文章目录1. 算法效率1.1 什么是时间复杂度1.2 常见结构的基本复杂度1.2.1 O(1)1.2.2 O(n)1.2.3 O(n²)1.2.4 O(log n)1.2.5 O(n log n)2. 什么是空间复杂度2.1 计算空间复杂度的三条前提前提一只算额外空间前提二看峰值不看累计前提三递归栈也要算2.2 O(1)2.3 O(n)2.4 空间复杂度速查表2.5 时间与空间的权衡3. 小结1. 算法效率当我们评价一个算法的优劣时通常会通过算法效率来评估。算法效率分为两部分时间效率算法运行时耗费的时间空间效率算法运行过程中额外耗费的存储空间但由于运行环境电脑性能、编程语言、编译器优化存在差异同一份代码在不同机器上的实际耗时可能相差几十倍直接测量并不可靠。因此我们通常采用事前分析估算的方法由此引出时间复杂度和空间复杂度。1.1 什么是时间复杂度通俗地讲时间复杂度就是当输入数据量变大时这段代码的运行时间增长得有多快。它不关心「跑一次要几秒」只关心「数据量翻倍时时间涨几倍」。常见从小到大排列O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)1.2 常见结构的基本复杂度代码结构操作次数复杂度几条语句与 n 无关常数O(1)for (i 0; i n; i)套一层nO(n)两层都跑 n 次n × nO(n²)每层 n但内层只跑到一半n²/2O(n²)每次砍一半n→n/2→n/4log₂nO(log n)1.2.1 O(1)与 n 无关的固定几条语句。voidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}intis_leap(intyear){return(year%40year%100!0)||year%4000;}1.2.2 O(n)单层循环intfind_max(int*arr,intn){intmax_valarr[0];// 1 次for(inti0;in;i)// n 次if(arr[i]max_val)// 每次 1 次比较max_valarr[i];// 偶尔 1 次returnmax_val;}递归intsum_to_n(intn){if(n0)return0;returnnsum_to_n(n-1);}1.2.3 O(n²)两层都跑满for(inti0;in;i)for(intj0;jn;j)count;// n × n n² 次内层只跑一半for(inti0;in;i)for(intji;jn;j)count;// n (n-1) … 1 n(n1)/2 次1.2.4 O(log n)每轮折半intcount0;intxn;while(x0){count;x/2;}1.2.5 O(n log n)外层 n 次 内层折半for(inti0;in;i){// 外层 n 次intxi;while(x0){// 内层 log i 次count;x/2;}}2. 什么是空间复杂度和时间复杂度类似空间复杂度也采用事前分析估算的方法衡量的是当输入规模 n 增大时算法额外占用的内存增长得有多快。计算方法与时间复杂度基本一致但有三条特有规则。2.1 计算空间复杂度的三条前提前提一只算额外空间默认不计入输入数据本身只算算法为了完成计算而额外申请的空间即辅助空间auxiliary space。intfind_max(int*arr,intn){intmax_valarr[0];// 唯一的额外变量for(inti0;in;i)if(arr[i]max_val)max_valarr[i];returnmax_val;}输入arr占O(n)但那是输入自带的。算法额外只用 1 个变量故空间复杂度为O(1)。前提二看峰值不看累计voidrun(intn){int*amalloc(n*sizeof(int));// 申请 n 个free(a);int*bmalloc(n*sizeof(int));// 再申请 n 个free(b);}累计申请了2n个元素但任何时刻最多只有 n 个同时存在所以空间复杂度是O(n)而不是O(2n)。前提三递归栈也要算intfact(intn){if(n1)return1;returnn*fact(n-1);}函数里只有一个参数看似O(1)实际是O(n)。因为每层递归都要把参数、返回地址、局部变量压入调用栈n 层调用同时存在栈深度 n故空间复杂度为O(n)。2.2 O(1)只使用固定几个变量称为原地in-place算法。voidswap(int*a,int*b){intt*a;*a*b;*bt;}voidreverse(int*arr,intn){inti0,jn-1;while(ij){inttarr[i];arr[i]arr[j];arr[j]t;i;j--;}}不论 n 是 10 还是 1000 万额外内存始终是几个字节故为O(1)。冒泡、插入、选择、堆排序都是O(1)空间的原地排序这是它们的重要优势。2.3 O(n)辅助数组int*copy_array(int*src,intn){int*dstmalloc(n*sizeof(int));for(inti0;in;i)dst[i]src[i];returndst;}新数组包含 n 个元素故为O(n)。递归深度为 nintsum_rec(intn){if(n0)return0;returnnsum_rec(n-1);}这里的分析重点不是时间而是空间时间每层做一次加法共 n 层 →O(n)空间n 层栈帧同时存在 →O(n)注意同一个函数可以有两个不同的复杂度。时间看「调用了多少次」空间看「同时存在多少层」。这正是 1.2.2 与 2.4 使用相似代码的原因。2.4 空间复杂度速查表写法空间复杂度几个局部变量O(1)| 一维数组 n 个元素 |O(n)|| 递归深度为 n |O(n)|2.5 时间与空间的权衡算法设计中时间和空间往往不能同时最优需要取舍因此「用空间换时间」是工程中最常见的优化方向因为内存通常比 CPU 时间便宜。3. 小结时间复杂度数操作次数随 n 的增长趋势。顺序相加、嵌套相乘、分支取最大、递归写递推式最后化简只留最高阶。空间复杂度数额外内存的峰值随 n 的增长趋势。只算额外空间看峰值不看累计递归要算栈深度。两者都是事前估算衡量的是增长趋势而非具体耗时或占用。判断依据是次数不是循环层数系数和常数不影响量级。