复杂度的概念

算法效率1.复杂度的概念算法在编写成可执行程序后需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法需要的额外空间。**2.**时间复杂度定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运⾏时间呢因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译器进⾏编译和新编译器编译在同样机器下运⾏时间不同。同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。. 并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢这个T(N)函数式计算了程序的执⾏次数。通过c语⾔编译链接章节学习我们知道算法程序被编译后⽣成⼆进制指令程序运⾏就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)假设每句指令执⾏时间基本⼀样(实际中有差别但是微乎其微)那么执⾏次数和运⾏时间就是等⽐正相关这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率⼀定优于算法b。//count执行次数:eg:voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;//执行了N^2次}}}for(intk0;k2*N;k){count;//执行了N次}intM10;while(M--){count;//执行了10次}分析T(N)N^22*N10N10 T(N)130N100 T(N)10210N1000 T(N)1002010 发现其实占主导影响的就是(N^ 2 ) (这里剧透一下复杂度为O(N^2)实际中我们计算时间复杂度时计算的也不是程序的精确的执⾏次数精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码编译出的指令条数都是不⼀样的)计算出精确的执⾏次数意义也不⼤因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级也就是当N不断变⼤时T(N)的差别上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数复杂度的表⽰通常使⽤⼤O的渐进表⽰法。3.1 实际中如何快速计算时间复杂度计算时间复杂度本质是估算算法属于哪个数量级那么我们实际中还需要先求出它的执行次数再求出 T(N) 吗这样就太麻烦了所以是不需要的我们其实可以直接计算。根据前面讲的规则总结一下f(N) → T(N)a. 我们只需要关注循环语句因为普通语句的执行次数都算是常数项可以忽略。b. 循环语句中我们只计算内部的一个基本语句执行次数即可其他语法叠加计算出的也是这个项的系数系数也是可以忽略的。如for(inti0;in;i){x;}我们直接计算x的执行次数为 N 即可i n和i也一起计算的话影响的也是系数系数最后还是被忽略掉了。c. 多个循环语句一般优先看嵌套层数最多的循环找出最高阶项。一般一层循环就是 O(N)两层就是 O(N^2)三层循环是 O(N^3)但是实际中需要都算一下因为有时一层循环不一定是 O(N)可能是 O(log2N)两层嵌套循环也可能不是 O(N^2)而是 O(N) 等等所以还是要计算具体的算法逻辑。常见的时间复杂度量级O(1) O(logN) O(N) O(N * logN) O(N^2) O(N^3) O(2^N) O(N!)3.⼤O的渐进表⽰法⼤O符号Big O notation是⽤于描述函数渐进⾏为的数学符号推导⼤O阶规则时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。即O(1)所以上方代码的时间复杂度N^ 22*N10,保留高阶项除去低阶项和常数项变为O(N^2)4.1 时间复杂度计算示例4.1.1voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d ,count);}Func2()执行的次数:T(N)2N10 根据规则即O(N)4.1.2voidFunc3(intN,intM){intcount0;for(intk0;k2*N;k){count;}for(intk0;kM;k){count;}printf(%d ,count);}Func3中因为不知道M和N的大小所以写成O(MN)4.1.3voidFunc4(intN,intM){intcount0;for(intk0;k100;k){count;}printf(%d ,count);}Finc4: O(1)4.1.4constchar*strchr(constchar*str,intcharacter){constchar*s_beginstr;while(*s_begin!character){if(*s_begin\0)returnNULL;s_begin;}returns_begin;}1若要查找的字符在字符串第⼀个位置则T (N) 12若要查找的字符在字符串最后的⼀个位置则T (N) N3若要查找的字符在字符串中间位置则T (N) N/24平均情况:(1234···n)*1/n(1n)/2因此strchr的时间复杂度分为最好情况 O(1)最坏情况 O(N)平均情况 O(N1/2) 即O(N)总结通过上⾯我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。最坏情况任意输⼊规模的最⼤运⾏次数(上界)平均情况任意输⼊规模的期望运⾏次数最好情况任意输⼊规模的最⼩运⾏次数(下界)⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界也就是最坏运⾏情况4.1.5voidBubbleSort(int*arr,intn){assert(arr);for(intnumn;n0;n--){intchange0;for(inti1;inum;n){if(arr[i-1]arr[i]){swap(arr[i-1],arr[i]);change1;}}if(change0)break;}}1若数组有序则T (N) N2若数组有序且为降序则T (N) (123…(n-1))n(n1)*1/2时间复杂度一般为最差情况即T(N)O(N^2)4.1.6voidtest(intn){intnum1;while(numn){num*2;}}n2时执⾏次数为1当n4时执⾏次数为2当n16时执⾏次数为4假设执⾏次数为 x 则 2x N因此执⾏次数 x logN因此test的时间复杂度取最差情况为O(logN)注意课件中和书籍中 log2N 、log N 、lgN表⽰当n接近⽆穷⼤时底数的⼤⼩对结果影响不⼤。因此⼀般情况下不管底数是多少都可以省略不写即可以表⽰为 (logN)不同书籍的表⽰⽅式不同以上写法差别不⼤我们建议使⽤ (logN)4.1.7递归函数intfunc(intn){if(0n)return1;returnfunc(n-1)n;}调用1次O(1),调用N次,即最坏情况:O(N)经典题目:下列函数的时间复杂度是intfunc(intn){inti0,sum0;while(sumn)sumi;returni;}本题要计算循环执⾏次数相⽐前⾯的题要绕⼀些假设循环执⾏x次本题中每次循环sum i的结果i0时sum1;i1时sum2;i2时sum3…ix-1时sumx循环结束时 sum 1 2 3 … x n则 (x1)x/2n则整体时间复杂度为 O(n^1/2)5. 空间复杂度空间复杂度也是⼀个数学表达式是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间因为常规情况每个对象⼤⼩差异不会很⼤所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使⽤⼤O渐进表⽰法。注意函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定5.1.1voidBubbleSort(int*arr,intn){assert(arr);for(intnumn;n0;n--){intchange0;for(inti1;inum;n){if(arr[i-1]arr[i]){swap(arr[i-1],arr[i]);change1;}}if(change0)break;}}函数栈帧在编译期间已经确定好了只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有change等有限个局部变量使⽤了常数个额外空间因此空间复杂度为 O(1)5.1.2intfunc(intn){if(0n)return1;returnfunc(n-1)n;}func递归调用了N次额外开辟了N个函数栈帧每个栈帧用了常数个空间,空间复杂度为O(N)递归算法的空间复杂度通用公式对于递归算法空间复杂度主要取决于递归调用的深度以及每次递归中额外开辟的空间。可以总结为递归算法的空间复杂度等于每一层递归额外空间之和再取大 O 渐进表示。举例说明intfunc(intn){if(0n)return1;returnfunc(n-1)n;}递归深度 M N每层递归只用了常数个局部变量即 M O(1)因此 S(N) O(N × 1) O(N)。再比如下面这个递归每层都开辟了一个大小为 N 的数组voidfunc(intn){if(n0)return;intarr[n];// 每层额外开辟 O(N) 空间func(n-1);}递归深度 M N每层额外空间 Mᵢ O(N)因此 S(N) O(N × N) O(N^2)。小结计算递归算法的空间复杂度时先看递归深度 M再看每层递归额外申请的空间 Mᵢ两者相乘求和后取最高阶即为最终的空间复杂度。注意函数调用时压栈的参数、返回地址等属于常数级开销通常可以忽略。越靠左算法越快越靠右越慢O(1) O(log n) O(n) O(n*log n) O(n^2) O(n^3) O(2^n) O(n!). 复杂度算法题 (引用)6.1 旋转数组给定⼀个整数数组 nums 将数组中的元素向右轮转 k 个位置其中 k 是⾮负数。如果我们采⽤每次将数组中数据右轮转⼀位轮转k次的思路则时间复杂度为O(N^2) 空间复杂度为 O(1)思路一时间复杂度O(N^2),循环K次将数组所有元素右移一位voidrotate(int*nums,intnumsSize,intk){intendnums[numsSize-1];while(k--){for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}思路二空间复杂度 O(N)申请新数组空间先将后k个数据放到新数组中再将剩下的数据挪到新数组中给定⼀个整数数组 nums 将数组中的元素向右轮转 k 个位置其中 k 是⾮负数.如果我们采⽤新的思路空间换时间开辟⼀个额外的跟nums⼀样⼤的临时数组tmp将nums的后k个数据挪动到tmp的前k个位置再将nums前n-k个挪动到tmp的后n-k个位置再将tmp数组中的值拷⻉回到nums数组则时间复杂度为 T (N) O(N) 空间复杂度为S(N) O(N)voidrotate(int*nums,intnumsSize,intk){k%numsSize;if(k0)return;inttmp[k];// 变长数组C99 起支持也可写成 int tmp[numsSize]// 拷贝 nums 中的后 k 个到 tmp 的前 k 个位置intj0;for(intinumsSize-k;inumsSize;i){tmp[j]nums[i];}// 从后往前拷贝 nums 前 n-k 个到后 n-k 个位置for(intinumsSize-k-1;i0;--i){nums[ik]nums[i];}// 将 tmp 数组中的值拷贝回到 nums 数组for(inti0;ik;i){nums[i]tmp[i];}}思路三空间复杂度 O(1)前n‑k个逆置4 3 2 1 5 6 7后k个逆置 4 3 2 1 7 6 5整体逆置 5 6 7 1 2 3 4给定⼀个整数数组 nums 将数组中的元素向右轮转 k 个位置其中 k 是⾮负数。 有没有既省空间⼜省时间的思路呢将nums中所有数据逆置⼀遍再分别前k个逆置和后n-k个逆置则时间复杂度为 T (N) O(N) 空间复杂度为 S(N) O(1)voidreverse(int*nums,intbegin,intend){while(beginend){inttmpnums[begin];nums[begin]nums[end];nums[end]tmp;begin;end--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;//整体逆置reverse(nums,0,numsSize‑k‑1);//后n-k个逆置reverse(nums,numsSize‑k,numsSize‑1);//前k个逆置reverse(nums,0,numsSize‑1);}