【数据结构与算法】 时间复杂度计算

👨‍💻 关于作者：会编程的土豆

“不是因为看见希望才坚持，而是坚持了才看见希望。”

你好，我是会编程的土豆，一名热爱后端技术的Java学习者。

📚正在更新中的专栏：

• 《数据结构与算法》

• 《leetcode hot 100》

💕作者简介：后端学习者

第一步：找出基本操作
找出代码中执行最频繁、最内层的操作，如加法、比较、赋值、数组访问等。

第二步：计算执行次数
分析代码结构，推导出基本操作的执行次数关于 nn 的函数 T(n)T(n)。

• 顺序结构：总次数是各步骤次数之和。

• 条件判断：取执行次数最多的分支。

• 循环：次数取决于循环变量和条件。

  • 单层循环，循环 mm 次：乘 mm。

  • 嵌套循环：相乘。

  • 循环变量变化不规律（如每次翻倍）：涉及对数。

第三步：保留最高次项，忽略常数
用大 OO 表示法简化 T(n)T(n)。
规则：去掉常数系数，只保留增长最快的项。

1.O(1) —— 常数阶

int getFirst(int arr[]) { return arr[0]; }

分析
无论数组多大，只执行一次数组访问 → O(1)。

2. O(n) —— 线性阶

int findMax(int arr[], int n) { int maxVal = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } return maxVal; }

分析
循环执行n-1次，每次比较 1 次 → 总操作次数 ~ n → O(n)。

3. O(n2) —— 平方阶

void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // 外层 n 次 for (int j = 0; j < n - i - 1; j++) { // 内层 ~ n 次 if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } }

分析
总比较次数 ≈ n(n−1)/2​ → 最高次项 n2→ O(n2)。

我们只数if (arr[j] > arr[j+1])这行比较语句的执行次数。

• 当i = 0时：内层循环j从 0 到n-2，比较了n-1次。

• 当i = 1时：内层循环j从 0 到n-3，比较了n-2次。

• 当i = 2时：内层循环比较了n-3次。

• ...

• 当i = n-2时：内层循环比较了1次。

所以，总的比较次数T(n)就是一个等差数列的和：
T(n) = (n-1) + (n-2) + ... + 1

根据高斯求和公式（首项加末项乘以项数除以2），这个和就等于n(n-1)/2。

1. 只保留最高次项：因为当n很大时，它决定了函数的增长趋势。丢掉- (1/2)n这个低次项。

2. 忽略最高次项的常数系数：因为系数不改变增长的趋势。丢掉1/2这个系数。

(1/2)n^2 - (1/2)n---> 保留最高次项(1/2)n^2---> 忽略系数1/2--->得到n^2

所以我们就说，这个冒泡排序算法的时间复杂度是O(n^2)。

4. O(log⁡n)—— 对数阶

int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

核心逻辑：log 就是在问“需要折半多少次？

举个例子：从 100 折半到 1

100 → 50 (折半1次) 50 → 25 (折半2次) 25 → 12 (折半3次) 12 → 6 (折半4次) 6 → 3 (折半5次) 3 → 1 (折半6次)

问：折半了多少次？答：6次

数学上，这就是在解方程：

100 × (1/2)^k = 1

也就是：

100 = 2^k

k = log₂(100) ≈ 6.64（取整就是6或7次）

所以规律是：

发现了吗？次数 = log₂(n)

一句话记住

log₂(n) 的定义就是：n 连续除以 2，多少次能变成 1

所以：

• 二分查找每次折半 → 需要 log n 次

• 二叉树每次分两叉 → 高度是 log n

• 任何"每次规模减半"的算法 → 复杂度都带 log

5. O(nlog⁡n) —— 线性对数阶

void weirdLoop(int n) { for (int i = 0; i < n; i++) { // n 次 int j = 1; while (j < n) { // log n 次 j *= 2; } } }

分析
外层 nn 次 × 内层 log⁡n 次 → O(nlogn)。

6. 递归复杂度（斐波那契）

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

分析
递归树是一棵二叉树，节点数 ~ 2n2n → O(2n)O(2n)（指数级，非常慢）。

7. 更好递归（备忘录优化 → O(n)）

int fibMemo(int n, int memo[]) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); }

分析
每个 n 只计算一次 → O(n)

总结表（C++ 版）