在编程的世界里,我们经常面临一个灵魂拷问:当用户从10个变成1000万个时,你的代码还能跑得动吗?
假设你正在整理一个图书馆:
这就引入了我们今天的主角——大O表示法。

简单来说,大O表示法(Big O Notation) 是程序员用来吐槽代码“效率”的一种通用语言。它不计算具体的秒数(因为不同的电脑运行速度不同),它计算的是趋势。
随着输入数据量(n)的增加,程序的运行时间或占用内存会变慢/变大多少?
为了方便理解,我们将常见的几种复杂度按“效率”从高到低排列:
含义: 不管数据有多少,耗时都一样。这是最理想的状态!
举例: 假设你知道朋友家的具体门牌号。无论这个城市有10个人还是1000万人,你都能直接导航到他家门口,不需要挨家挨户找。
|#include <vector> using namespace std; int getFirstElement(const vector<int>& arr) { // 就像你有任意门的钥匙,直接到达目的地 return arr[0]; } // 无论数组里有10个数据还是10亿个,这一步操作瞬间完成。 // 这就是O(1)的特征:时间不随输入规模变化
含义: 数据量翻倍,时间只增加一点点。通常出现在“二分查找”中。
举例: 猜数字游戏(1-100)。 你问:“是50吗?” 对方:“低了”。 你瞬间排除了1-50这一半的数字!每次都能排除一半的可能性,这效率极高。
|#include <vector> using namespace std; // 二分查找:经典的 O(log n) int binarySearch(const vector<int>& sortedArr, int target) { int left = 0; int right = sortedArr.size() - 1; while (left <= right) { int mid = (left + right) / 2; // 每次都砍一半! if (sortedArr[mid] == target) { return mid; // 找到了! } else if (sortedArr[mid] < target) { left = mid + 1; // 扔掉左边那一半 } else { right = mid - 1; // 扔掉右边那一半 } } return -1; } // 即使有100万个数据,最多也只需要找约20次!
含义: 数据量增加几倍,耗时就增加几倍。中规中矩。
举例: 看书。书越厚,看完需要的时间就越长。如果你要在一本没目录的书里找一句话,最坏的情况必须从第一页翻到最后一页。
|#include <vector> using namespace std; int findElement(const vector<int>& arr, int target) { // 必须老老实实从头走到尾 for (int i = 0; i < arr.size(); i++) { if (arr[i] == target) { return i; } } return -1; } // 数据量n越大,循环次数越多,成正比 -> O(n)
含义: 数据量增加,耗时呈指数级爆炸增长。通常涉及“双层循环”。
举例: 班级聚会握手。 班里有n个同学,每个人都要和其余n-1个同学握手。 如果是10人,握手次数还好;如果是1000人,握手次数就是百万级的!
|#include <vector> using namespace std; // 冒泡排序:典型的 O(n²) void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { // 外层:每个人都要轮一遍 for (int j = 0; j < n - i - 1; j++) { // 内层:又要和剩下的人比一遍 if (arr[j] > arr[j + 1]) { // 交换位置 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // 循环套循环,n * n = n² 次操作。 // 数据量稍微大一点,程序就会卡死。
假设你日后要做一个“商品搜索”功能,超市有100万件商品。
结论: 好的算法(低时间复杂度)能帮你省下巨额的服务器费用,还能让用户觉得你的软件“真快”!
除了关心“快不快”(时间),我们还得关心“占地大不大”(内存)。这就是 空间复杂度。
举例:搬家
示例对比:
|// 🟢 省空间:选择排序 // 只用了一个临时变量 temp,无论数组多大,额外空间都是固定的 O(1) void selectionSort(vector<int>& arr) { // ... 直接在原数组 arr 上修改 ... } // 🔴 费空间:归并排序 // 需要创建新的 vector (left, right) 来暂存数据 // 数据越多,需要的额外内存越大 -> O(n) vector<int> mergeSort(const vector<int>& arr) { vector<int> left = ...; // 申请新内存 vector<int> right = ...; // 申请新内存 return merge(left, right); }
在现在的计算机设备上,内存通常比较充足,所以有时候为了追求极致的速度(时间),我们会愿意牺牲一些内存(空间)。这就是传说中的**“空间换时间”**。
4. 分析函数的时间复杂度练习
分析以下函数的时间复杂度:
sumArray 函数遍历数组一次,计算所有元素的和mysteryFunction 函数中,循环变量每次乘以2(1, 2, 4, 8...)|#include <iostream> #include <vector> using namespace std; // 函数A:计算数组和 int sumArray(const vector<int>& arr) { int sum = 0; for (int i = 0; i < arr.size(); i++) // 循环 n 次 { sum += arr[i]; // 每次循环执行常数时间操作 } return sum; } // 时间复杂度:O(n) // 原因:循环执行 n 次,每次循环是常数时间操作 // 就像把书从头翻到尾,需要翻 n 页 // 函数B:神秘函数 void mysteryFunction(int n) { for (int i = 1; i < n; i *= 2) // 注意 i 每次乘以 2 { cout << i << " "; } } // 时间复杂度:O(log n) // 原因:循环变量每次乘以 2(1, 2, 4, 8, 16...) // 需要 log₂(n) 次循环才能达到 n // 就像切蛋糕每次切一半,切 log₂(n) 次就切完了 int main() { vector<int> arr = { 1, 2, 3, 4, 5 }; cout << "数组和: " << sumArray(arr) << endl; cout << "MysteryFunction(16): "; mysteryFunction(16); // 输出: 1 2 4 8 cout << endl; return 0; }
|数组和: 15 MysteryFunction(16): 1 2 4 8
说明:
5. 斐波那契数列的陷阱练习
实现斐波那契数列的两个版本,对比它们的性能差异:
fibonacci(10) 和 fibonacci(40),观察性能差异|#include <iostream> #include <vector> #include <chrono> using namespace std; using namespace std::chrono; // 版本1:递归版本(无记忆化)- 时间复杂度 O(2ⁿ) long long fibonacciRecursive(int n) { if (n <= 1) return n; // 问题:会重复计算大量子问题 // 例如:fib(5) = fib(4) + fib(3) // fib(4) = fib(3) + fib(2) // fib(3) = fib(2) + fib(1) // 可以看到 fib(3) 和 fib(2) 被重复计算了 return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); } // 版本2:动态规划版本 - 时间复杂度 O(n) long long fibonacciDP(int n) { if (n <= 1) return n; // 用数组记录已计算的值,避免重复计算 vector<long long> dp(n + 1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } int main() { // 测试小数值 cout << "计算 fibonacci(10):" << endl; auto start1 = high_resolution_clock::now(); long long result1 = fibonacciRecursive(10); auto end1 = high_resolution_clock::now(); auto duration1 = duration_cast<milliseconds>(end1 - start1); cout << "递归版本: " << result1 << ", 耗时: " << duration1.count() << "ms" << endl; auto start2 = high_resolution_clock::now(); long long result2 = fibonacciDP(10); auto end2 = high_resolution_clock::now(); auto duration2 = duration_cast<milliseconds>(end2 - start2); cout << "动态规划版本: " << result2 << ", 耗时: " << duration2.count() << "ms" << endl; // 测试较大值(递归版本会很慢) cout << "\n计算 fibonacci(40):" << endl; auto start3 = high_resolution_clock::now(); long long result3 = fibonacciDP(40); auto end3 = high_resolution_clock::now(); auto duration3 = duration_cast<milliseconds>(end3 - start3); cout << "动态规划版本: " << result3 << ", 耗时: " << duration3.count() << "ms" << endl; cout << "\n注意:递归版本计算 fibonacci(40) 可能需要几分钟甚至更久!" << endl; cout << "这是因为递归版本的时间复杂度是指数级的 O(2ⁿ)" << endl; return 0; }
说明:
fib(3) 会被计算多次fibonacci(50) 可能需要几年时间fibonacci(50) 只需要几毫秒