【算法】小白也能懂 · 第 1 节时间复杂度与空间复杂度学算法的第一步不是急着刷题而是搞懂两个概念时间复杂度和空间复杂度。它们是衡量算法好不好的核心指标。理解了这两个概念你才能判断一个算法是快还是慢、是省内存还是费内存。1. 为什么要学复杂度假设你写了一个程序处理 1000 条数据跑了 1 秒。那处理 100 万条数据要多久如果你的算法是好的可能只要 1000 秒如果你的算法是差的可能要 100 万秒约 11.5 天复杂度分析就是帮你在写代码之前就能预估这个算法处理大数据量时表现如何。2. 大 O 表示法复杂度用大 O 表示法来描述写成O(某个表达式)。它描述的是当输入数据量n变大时算法的运行时间或内存占用增长的趋势。注意大 O 关心的是增长趋势不是精确的运行时间。同样输入 1000 条数据O(n)的算法可能实际跑了 2 秒O(n²)的算法跑了 0.5 秒——但当n增长到 100 万时O(n)一定比O(n²)快得多。3. 常见的时间复杂度从快到慢排列我们逐个来看。3.1 O(1)常数时间不管数据量多大执行时间都一样。intgetFirst(intarr[],intn){returnarr[0];// 直接取第一个元素一步到位}这是最快的情况不管数组有 10 个还是 1000 万个元素都是一步完成。3.2 O(log n)对数时间每次把问题规模缩小一半。典型例子是二分查找。intbinarySearch(intarr[],intn,inttarget){intleft0,rightn-1;while(leftright){intmidleft(right-left)/2;if(arr[mid]target)returnmid;elseif(arr[mid]target)leftmid1;elserightmid-1;}return-1;}假设数组有 1024 个元素最多只需要比较 10 次因为 2¹⁰ 1024。数据量翻倍查找次数只多 1 次。非常高效。3.3 O(n)线性时间数据量翻倍时间也翻倍。最典型的就是遍历数组。intfindMax(intarr[],intn){intmaxValarr[0];for(inti1;in;i){if(arr[i]maxVal)maxValarr[i];}returnmaxVal;}每个元素看一遍数据量越大花的时间越多但增长是线性的、可接受的。3.4 O(n log n)线性对数时间很多高效排序算法的时间复杂度就是O(n log n)比如归并排序、快速排序。// 归并排序的核心思想伪代码voidmergeSort(intarr[],intn){if(n1)return;// 1. 分成两半// 2. 递归排序左半部分O(n/2 * log(n/2))// 3. 递归排序右半部分O(n/2 * log(n/2))// 4. 合并两个有序数组O(n)// 总计O(n log n)}O(n log n)被认为是比较排序的理论下限也就是说基于比较的排序算法不可能比这个更快了。3.5 O(n²)平方时间嵌套循环外层遍历一遍内层再遍历一遍。典型的冒泡排序voidbubbleSort(intarr[],intn){for(inti0;in-1;i){for(intj0;jn-1-i;j){if(arr[j]arr[j1]){// 交换inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}}1000 个元素需要约 100 万次操作100 万个元素需要约 1 万亿次操作。数据量大了就很慢。3.6 O(2ⁿ) 和 O(n!)指数级和阶乘级这两种复杂度在数据量稍大时就完全不可用了。O(2ⁿ)每增加一个数据时间翻倍。典型例子是暴力求解子集问题。O(n!)典型例子是暴力求解全排列。20 个元素的全排列就有 20! ≈ 2.4 × 10¹⁸ 种算到天荒地老。4. 时间复杂度速查表复杂度名称n 1000 时的大致操作数常见算法O(1)常数1哈希表查找O(log n)对数10二分查找O(n)线性1000遍历数组O(n log n)线性对数10000归并排序O(n²)平方1000000冒泡排序O(2ⁿ)指数2¹⁰⁰⁰天文数字暴力子集5. 空间复杂度空间复杂度描述的是算法运行时需要多少额外内存。表示方法和时间复杂度一样也是大 O。5.1 O(1) 空间只用了固定几个变量不管数据量多大intsum(intarr[],intn){inttotal0;// 一个变量for(inti0;in;i)totalarr[i];returntotal;}5.2 O(n) 空间创建了一个和原数据等大的新数组int*copyArray(intarr[],intn){int*newArrnewint[n];// 新建了 n 大小的数组for(inti0;in;i)newArr[i]arr[i];returnnewArr;}5.3 递归的空间复杂度递归调用会在调用栈上占用空间。比如递归版的阶乘intfactorial(intn){if(n1)return1;returnn*factorial(n-1);}调用factorial(5)会在栈上产生 5 层调用空间复杂度是O(n)。6. 如何分析复杂度几个实用技巧看循环嵌套层数一层循环通常是O(n)两层嵌套通常是O(n²)看有没有缩小一半的操作有就是O(log n)看有没有新建数组/容器判断空间复杂度取最大的那个如果一个函数里有O(n)和O(n²)两段代码总复杂度取O(n²)7. 总结这一节我们学了大 O 表示法是什么它关心的是增长趋势6 种常见时间复杂度O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)空间复杂度的概念和分析方法分析复杂度的实用技巧记住一句话好的算法 在正确解决问题的前提下时间和空间复杂度尽可能低。下一节我们学习数组双指针技巧这是一种非常实用的算法思维敬请期待