时间复杂度学习笔记

一、大O渐进表示法规则

时间复杂度和空间复杂度一般都用大O的渐进表示法进行表示，规则如下：

1. 所有常数都用常数1表示。
2. 只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项的系数，得到的结果就是大O阶。

二、时间复杂度的定义

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但这很麻烦，所以才有了时间复杂度这个分析方式。

一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。

三、数学公式参考

3.1 等差数列

• 通项公式：aₙ = a₁ + (n-1)d （d 为公差）
• 前 n 项和：Sₙ = n(a₁ + aₙ) / 2

3.2 等比数列

• 通项公式：aₙ = a₁ · qⁿ⁻¹ （q 为公比）
• 前 n 项和：Sₙ = a₁(1 - qⁿ) / (1 - q) （q ≠ 1）

四、例题详解

例题 1：对数型 — 除法递减

代码：

i = n * n;
while (i != 1) {
    i = i / 2;
}

分析过程：

• 初始值：i = n²

• 循环规律：每次循环 i 除以 2，即 i = n²/2, n²/4, n²/8, …

• 设循环执行了 k 次后 i = 1，则：

  n² / 2ᵏ = 1 → 2ᵏ = n² → k = log₂(n²) = 2·log₂n

• 根据大O规则（去除系数），时间复杂度为：O(log n)

例题 2：对数型 — 乘法递增

代码：

int i = 1;
while (i < n) {
    i = i * 2;
}

分析过程：

• 初始值：i = 1

• 循环规律：每次循环 i 乘以 2，即 i = 1, 2, 4, 8, …

• 设循环执行了 k 次后退出，则：

  2ᵏ ≥ n → k = log₂n

• 时间复杂度为：O(log n)

例题 3：平方根型 — 二次增长判断

代码：

x = 0;
while (n >= (x + 1) * (x + 1)) {
    x = x + 1;
}

分析过程：

• 初始值：x = 0

• 循环规律：每次循环 x 加 1

• 设循环执行了 k 次后退出，则退出条件为 (x+1)² ≥ n，即：

  (x + 1)² ≈ n → x + 1 = √n → x = √n - 1

• 循环执行了 √n - 1 次，时间复杂度为：O(√n)

例题 4：嵌套循环 — 多项式型

代码：

int m = 0;
for (i = 1; i < n; i++) {
    for (j = 1; j <= 2 * n; j++) {
        m++;
    }
}

分析过程：

• 外层循环：i 从 1 到 n-1，执行 n-1 次

• 内层循环：j 从 1 到 2n，每次执行 2n 次

• 基本操作 m++ 的总执行次数：

  (n - 1) × 2n = 2n² - 2n

• 根据大O规则（只保留最高阶项 2n²，去除系数 2），时间复杂度为：O(n²)

例题 5：嵌套循环 — 等比数列求和

代码：

int k = 1;
while (k < n) {
    for (int i = 0; i < k; i++) {
        操作;
    }
    k *= 2;
}

分析过程：

• 外层 while 循环：k 取值 1, 2, 4, 8, …, 直到 k ≥ n

• 内层 for 循环：分别执行 1, 2, 4, 8, … 次

• 设 k 最大取值为 2ᵐ（2ᵐ < n），则总执行次数为等比数列求和：

  S = 1 + 2 + 4 + 8 + … + 2ᵐ = 2ᵐ⁺¹ - 1

• 由于 2ᵐ < n，所以 2ᵐ⁺¹ < 2n，因此 S < 2n - 1

• 根据大O规则，时间复杂度为：O(n)

例题 6：递归函数 — 指数型（斐波那契类）

代码：

public int a(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return a(n - 1) + a(n - 2);
    }
}

分析过程：

• 递归调用树展开：

  • a(n) → a(n-1) + a(n-2)
  • a(n-1) → a(n-2) + a(n-3)
  • a(n-2) → a(n-3) + a(n-4)
  • …

• 递归树是一棵二叉树，深度为 n，每层节点数约 2ᵏ（k 为层数）

• 总节点数约为 2ⁿ - 1

• 时间复杂度为：O(2ⁿ)

五、总结对照表

六、核心技巧归纳

1. 除法/乘法递增：若变量每次除以或乘以常数 c（c > 1），则循环次数为 O(log n)。
2. 嵌套循环：外层循环次数 × 内层循环次数 = 总执行次数。
3. 等比数列求和：若内层循环次数呈等比数列增长，用等比数列求和公式化简。
4. 递归函数：画出递归调用树，按二叉树节点数估算，通常为 O(2ⁿ) 量级。
5. 大O简化三步走：去常数 → 留最高阶 → 去系数。

七、常见时间复杂度速查