企业官网建设流程全解析

【算法】小白也能懂 · 第 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){intleft=0,right=n-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target)returnmid;elseif(arr[mid]<target)left=mid+1;elseright=mid-1;}return-1;}

假设数组有 1024 个元素，最多只需要比较 10 次（因为 2¹⁰ = 1024）。数据量翻倍，查找次数只多 1 次。非常高效。

3.3 O(n)：线性时间

数据量翻倍，时间也翻倍。最典型的就是遍历数组。

intfindMax(intarr[],intn){intmaxVal=arr[0];for(inti=1;i<n;i++){if(arr[i]>maxVal)maxVal=arr[i];}returnmaxVal;}

每个元素看一遍，数据量越大，花的时间越多，但增长是线性的、可接受的。

3.4 O(n log n)：线性对数时间

很多高效排序算法的时间复杂度就是O(n log n)，比如归并排序、快速排序。

// 归并排序的核心思想（伪代码）voidmergeSort(intarr[],intn){if(n<=1)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(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){// 交换inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}

1000 个元素需要约 100 万次操作，100 万个元素需要约 1 万亿次操作。数据量大了就很慢。

3.6 O(2ⁿ) 和 O(n!)：指数级和阶乘级

这两种复杂度在数据量稍大时就完全不可用了。

• O(2ⁿ)：每增加一个数据，时间翻倍。典型例子是暴力求解子集问题。
• O(n!)：典型例子是暴力求解全排列。20 个元素的全排列就有 20! ≈ 2.4 × 10¹⁸ 种，算到天荒地老。

4. 时间复杂度速查表

5. 空间复杂度

空间复杂度描述的是算法运行时需要多少额外内存。表示方法和时间复杂度一样，也是大 O。

5.1 O(1) 空间

只用了固定几个变量，不管数据量多大：

intsum(intarr[],intn){inttotal=0;// 一个变量for(inti=0;i<n;i++)total+=arr[i];returntotal;}

5.2 O(n) 空间

创建了一个和原数据等大的新数组：

int*copyArray(intarr[],intn){int*newArr=newint[n];// 新建了 n 大小的数组for(inti=0;i<n;i++)newArr[i]=arr[i];returnnewArr;}

5.3 递归的空间复杂度

递归调用会在调用栈上占用空间。比如递归版的阶乘：

intfactorial(intn){if(n<=1)return1;returnn*factorial(n-1);}

调用factorial(5)会在栈上产生 5 层调用，空间复杂度是O(n)。

6. 如何分析复杂度

几个实用技巧：

1. 看循环嵌套层数：一层循环通常是O(n)，两层嵌套通常是O(n²)
2. 看有没有"缩小一半"的操作：有就是O(log n)
3. 看有没有新建数组/容器：判断空间复杂度
4. 取最大的那个：如果一个函数里有O(n)和O(n²)两段代码，总复杂度取O(n²)

7. 总结

这一节我们学了：

• 大 O 表示法是什么，它关心的是增长趋势
• 6 种常见时间复杂度：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)
• 空间复杂度的概念和分析方法
• 分析复杂度的实用技巧

记住一句话：好的算法 = 在正确解决问题的前提下，时间和空间复杂度尽可能低。

下一节我们学习数组双指针技巧，这是一种非常实用的算法思维，敬请期待！