1. 确定输入规模（n）

• 明确问题规模的定义（如数组长度、矩阵维度、树节点数等）。
• 例如：排序算法中，n 通常指待排序元素的数量。

---

2. 识别基本操作

• 找到算法中执行次数最多的操作（如比较、赋值、循环迭代等）。
• 例如：排序算法中的比较操作，搜索算法中的循环迭代。

---

3. 建立执行次数的数学表达式

• 统计基本操作的执行次数，将其表示为输入规模 n 的函数 T(n)。
• 常见情况：
  • 顺序结构：执行次数相加。
  • 分支结构：取最坏情况下的分支。
  • 循环结构：分析循环次数与 n 的关系（重点关注循环变量如何变化）。
  • 递归算法：通过递归方程（递推关系式）描述时间。

---

4. 用大O表示法简化

• 保留最高阶项：忽略低阶项和常数系数。
  • 例如：T(n) = 3n² + 5n + 2 → O(n²)。
• 常见复杂度等级（从优到劣）：
  • O(1)（常数）→ O(log n)（对数）→ O(n)（线性）→ O(n log n) → O(n²)（平方）→ O(2ⁿ)（指数）。

第一步：理解基本概念

时间复杂度：描述算法运行时间与输入规模 n 的增长关系，用 大O符号（O） 表示。
核心思想：忽略常数和低阶项，只保留最高阶项，例如 3n² + 5n + 10 → O(n²)。

---

第二步：找出代码中的“基本操作”

基本操作是执行次数最多的核心操作，通常是循环或递归内的操作。
示例1：循环中的加法操作

c复制代码

int sum = 0;
for(int i=0; i<n; i++) {  // 循环n次
    sum += i;              // ← 基本操作（执行n次）
}

时间复杂度：O(n)

---

第三步：分析循环结构

1. 单层循环

c复制代码

for(int i=0; i<n; i++) {
    printf("%d", i);  // 执行n次
}

数学表达式：n次 → O(n)

---

2. 双重循环（独立变量）

c复制代码

for(int i=0; i<n; i++) {       // 外层n次
    for(int j=0; j<m; j++) {   // 内层m次
        printf("%d", i*j);     // 执行n×m次
    }
}

数学表达式：n × m次

• 若m与n无关 → O(nm)
• 若m = n → O(n²)

---

3. 双重循环（变量相关）

c复制代码

for(int i=0; i<n; i++) {       // 外层n次
    for(int j=0; j<i; j++) {   // 内层i次（i从0到n-1）
        printf("%d", j);       // 总次数：0+1+2+...+(n-1) = n(n-1)/2
    }
}

数学推导：
总次数 = Σi=0n-1 i = n(n-1)/2
简化：保留最高阶项并去掉系数 → O(n²)

---

4. 对数循环（变量倍增/倍减）

c复制代码

for(int i=1; i<=n; i*=2) {  // 循环次数：log₂n
    printf("%d", i);         // 执行log₂n次
}

数学推导：
i的变化：1 → 2 → 4 → 8 → ... → 2k ≤ n
解得 k = log₂n → O(log n)

---

第四步：递归算法分析

1. 单次递归调用（线性递归）

c复制代码

void func(int n) {
    if(n <= 0) return;
    printf("%d", n);      // O(1)操作
    func(n-1);            // 递归调用n次
}

递推公式：
T(n) = T(n-1) + 1
T(0) = 0
解得：T(n) = n → O(n)

---

2. 多次递归调用（指数级复杂度）

c复制代码

int fib(int n) {
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 每次调用产生2次递归
}

递推公式：
T(n) = T(n-1) + T(n-2) + 1
近似解：T(n) ≈ 2n → O(2ⁿ)

---

第五步：分治算法（主定理应用）

主定理公式：解决形如 T(n) = aT(n/b) + O(nd) 的递归式

• 若 a > bd → O(nlogba)
• 若 a = bd → O(nd log n)
• 若 a < bd → O(nd)

示例：归并排序

c复制代码

void merge_sort(int arr[], int l, int r) {
    if(l >= r) return;
    int m = l + (r-l)/2;
    merge_sort(arr, l, m);     // T(n/2)
    merge_sort(arr, m+1, r);   // T(n/2)
    merge(arr, l, m, r);       // O(n)
}

递推公式：T(n) = 2T(n/2) + O(n)
应用主定理：a=2, b=2, d=1 → 2 > 21 不成立 → 实际解为 O(n log n)（属于主定理第二种情况）

---

第六步：实战练习

示例代码

c复制代码

void mystery(int n) {
    int count = 0;
    for(int i=1; i<=n; i*=3) {       // 外层循环
        for(int j=0; j<i; j++) {     // 内层循环
            count++;
        }
    }
}

逐步分析

1. 外层循环次数：
   i的变化：1 → 3 → 9 → ... → 3k ≤ n
   解得循环次数：k = log₃n ≈ O(log n)

2. 内层循环次数：

   • 当i=1时，内层循环执行1次
   • 当i=3时，内层循环执行3次
   • ...
   • 总次数 = 1 + 3 + 9 + ... + 3log₃n

3. 等比数列求和：
   总和 S = (3k+1 - 1)/(3-1) = (3n - 1)/2 ≈ O(n)

4. 最终复杂度：外层O(log n) × 内层O(n) → O(n log n)

---

第七步：复杂度速查表

代码模式	时间复杂度	示例
单层循环	O(n)	for(int i=0; i<n; i++)
双重独立循环	O(n²)	冒泡排序
外层n次，内层log n次	O(n log n)	归并排序
变量每次翻倍的循环	O(log n)	二分查找
递归调用分支数为2	O(2ⁿ)	斐波那契数列（递归）
分治算法（主定理Case 2）	O(n log n)	快速排序（平均情况）

---

第八步：常见误区

1. 误将break语句视为优化：

   c复制代码

   for(int i=0; i<n; i++) {
       if(i == 5) break;  // 虽然提前终止，但复杂度仍为O(n)
   }

2. 混淆平均和最坏情况：

   c复制代码

   // 快速排序最坏O(n²)，平均O(n log n)

3. 忽略递归的隐藏成本：

   c复制代码

   void func(int n) {
       if(n > 0) {
           printf("%d", n);  // 看似O(1)，实际递归调用n次 → O(n)
           func(n-1);
       }
   }

 如何计算循环次数：分步详解与示例

1. 基础概念

• 循环次数：指循环体内的代码实际执行的次数，直接影响算法的时间复杂度。
• 关键要素：循环变量的 初始值、终止条件 和 更新方式。

---

2. 单层循环的计算方法

示例1：线性递增循环

c复制代码

for(int i=0; i<n; i++) {  // i从0到n-1
    printf("%d", i);
}

• 分析步骤：
  1. 初始值：i=0
  2. 终止条件：i < n
  3. 更新方式：i++（每次+1）
  4. 循环次数：当i取值0,1,2,...,n-1时执行，共 n次。
• 数学公式：循环次数 = 终止值 - 初始值 = n - 0 = n
• 时间复杂度：O(n)

---

示例2：倍增循环（对数级）

c复制代码

for(int i=1; i<=n; i*=2) {  // i每次乘以2
    printf("%d", i);
}

• 分析步骤：
  1. 初始值：i=1
  2. 终止条件：i <= n
  3. 更新方式：i *= 2（每次翻倍）
  4. 循环变量变化：1 → 2 → 4 → 8 → ... → 2^k ≤ n
  5. 求解次数k：
     由 2^k ≤ n 得 k ≤ log₂n → 循环次数 = ⌊log₂n⌋ + 1
• 时间复杂度：O(log n)

---

3. 嵌套循环的计算方法

示例3：独立嵌套循环（乘法法则）

c复制代码

for(int i=0; i<n; i++) {        // 外层n次
    for(int j=0; j<m; j++) {    // 内层m次
        printf("%d", i+j);
    }
}

• 总次数：外层n次 × 内层m次 = n×m次
• 时间复杂度：O(n×m)
  （若m与n无关）
  若m=n → O(n²)

---

示例4：依赖外层变量的嵌套循环（求和法则）

c复制代码

for(int i=0; i<n; i++) {        // 外层n次
    for(int j=0; j<i; j++) {    // 内层i次（i从0到n-1）
        printf("%d", j);
    }
}

• 总次数计算：
  • 当i=0时，内层执行0次
  • 当i=1时，内层执行1次
  • ...
  • 当i=n-1时，内层执行n-1次
  • 总次数 = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2
• 数学公式：等差数列求和公式
  S = Σ_{k=0}^{n-1} k = n(n-1)/2
• 时间复杂度：O(n²)

---

4. 复杂循环模式

示例5：内层循环变量非线性变化

c复制代码

for(int i=0; i<n; i++) {        // 外层n次
    for(int j=1; j<n; j*=2) {   // 内层log₂n次
        printf("%d", i*j);
    }
}

• 总次数：外层n次 × 内层log₂n次 = n log n次
• 时间复杂度：O(n log n)

---

示例6：多层循环混合模式

c复制代码

for(int i=1; i<=n; i++) {         // 外层n次
    for(int j=1; j<=i; j*=2) {    // 内层log₂i次
        printf("%d", j);
    }
}

• 总次数计算：
  • 外层i从1到n，内层循环次数为log₂i + 1次（例如i=8时，j=1,2,4,8，循环4次=log₂8+1）
  • 总次数 ≈ Σ_{i=1}^n log₂i ≈ n log n - n（斯特林公式近似）
• 时间复杂度：O(n log n)

Step 1：明确循环结构

for(int i=1; i<=n; i++) {         // 外层循环：执行n次
    for(int j=1; j<=i; j*=2) {    // 内层循环：每次执行次数与i相关
        printf("%d", j);
    }
}

---

Step 2：分析内层循环次数

内层循环 j=1; j<=i; j*=2 的规律：

• 每次循环 j 的值：1 → 2 → 4 → 8 → ... → 2^k ≤ i
• 循环次数：当 2^k > i 时终止，因此循环次数为 ⌊log₂i⌋ +1
  （参考之前的单循环分析）

结论：内层循环的时间复杂度为 O(log i)。

---

Step 3：计算总操作次数

外层循环 i 从 1 遍历到 n，每次内层循环执行 O(log i) 次。
总操作次数为：
T(n)=∑i=1n(内层循环次数)=∑i=1nlog⁡iT(n)=∑i=1n​(内层循环次数)=∑i=1n​logi

---

Step 4：简化求和公式

我们需要估算 ∑log i (i=1到n) 的量级。这里有两个关键方法：

方法 1：直接比较上下界

• 下界：当 i >= n/2 时，log i >= log(n/2) = log n -1
  共有 n/2 项满足此条件，因此总和至少为：

  ∑i=n/2nlog⁡i≥n2(log⁡n−1)=O(nlog⁡n)i=n/2∑n​logi≥2n​(logn−1)=O(nlogn)

• 上界：对所有 i <= n，log i <= log n
  总和至多为：

  ∑i=1nlog⁡i≤nlog⁡n=O(nlog⁡n)i=1∑n​logi≤nlogn=O(nlogn)

结论：总和的量级为 O(n log n)。

方法 2：利用对数的性质

∑i=1nlog⁡i=log⁡(1×2×3×...×n)=log⁡(n!)∑i=1n​logi=log(1×2×3×...×n)=log(n!)
通过斯特林公式近似（Stirling's approximation）：
n!≈2πn(ne)n  ⟹  log⁡(n!)≈nlog⁡n−nn!≈2πn​(en​)n⟹log(n!)≈nlogn−n
忽略低阶项后得到：
log⁡(n!)=O(nlog⁡n)log(n!)=O(nlogn) 

Step 4 分解：为什么 ∑log i = O(n log n)？

1. 将求和转换为乘积的对数

首先，观察求和公式：
∑i=1nlog⁡i=log⁡1+log⁡2+log⁡3+⋯+log⁡n∑i=1n​logi=log1+log2+log3+⋯+logn
利用对数的性质 log a + log b = log(ab)，可以将求和转换为乘积的对数：
∑i=1nlog⁡i=log⁡(1×2×3×⋯×n)=log⁡(n!)∑i=1n​logi=log(1×2×3×⋯×n)=log(n!)
（因为 1×2×3×…×n = n!）

---

2. 斯特林公式的作用

斯特林公式（Stirling’s approximation）是对 n! 的近似表达式：
n!≈2πn(ne)nn!≈2πn​(en​)n
取对数后：
log⁡(n!)≈log⁡(2πn(ne)n)log(n!)≈log(2πn​(en​)n)
展开计算：
log⁡(n!)≈12log⁡(2πn)+nlog⁡n−nlog(n!)≈21​log(2πn)+nlogn−n
忽略低阶项（log n 和常数）后：
log⁡(n!)≈nlog⁡n−n=O(nlog⁡n)log(n!)≈nlogn−n=O(nlogn)

---

3. 直观理解

• 当 n 很大时：n! 的增长速度接近 n^n，但比 n^n 慢一些。
  通过斯特林公式可知，log(n!) 的主要贡献来自 n log n，而 -n 是次要项。
• 示例验证：
  • n=100：
    log(100!) ≈ 363.7
n log n = 100 * 6.64 ≈ 664
n log n -n ≈ 664 - 100 = 564
    虽然数值不完全匹配，但量级（百位级）一致。
    （注：实际计算中斯特林公式更精确）

---

4. 为什么可以忽略低阶项？

在时间复杂度分析中，大 O 表示法只关心最高阶的项。例如：
log⁡(n!)≈nlog⁡n−n+12log⁡(2πn)log(n!)≈nlogn−n+21​log(2πn)

• n log n 是主导项，增长最快。
• -n 和 log n 的增长速度远小于 n log n（例如，当 n=1000 时，n log n ≈ 10,000，而 n=1000 本身只有 1000）。
• 因此，时间复杂度为 O(n log n)。

---

关键总结

• ∑log i = log(n!) → 通过斯特林公式简化为 O(n log n)。
• 为什么 "+1" 或其他低阶项不影响结果？
  因为大 O 表示法只保留最高阶的项，忽略常数和低阶项。

---

Step 5：验证示例

以 n=4 和 n=8 为例：

• n=4：

  • i=1 → 内层循环1次（log₂1=0 → 0+1=1）
  • i=2 → 内层循环2次（log₂2=1 → 1+1=2）
  • i=3 → 内层循环2次（log₂3≈1.58 → 取整后+1=2）
  • i=4 → 内层循环3次（log₂4=2 → 2+1=3）
  • 总操作次数：1+2+2+3=8
    n log n = 4 * 2 = 8（完全一致）

• n=8：

  • 内层循环次数分别为：1,2,2,3,3,3,3,4
  • 总操作次数：1+2+2+3+3+3+3+4=21
    n log n = 8 * 3 = 24（量级一致）

---

最终结论

总时间复杂度为 O(n log n)，因为：

1. 内层循环的代价为 O(log i)
2. 所有内层循环的总和 ∑log i 的量级为 O(n log n)

---

为什么不是 O(n) 或 O(log n)？

• 如果是 O(n)：外层循环 n 次，内层每次需要常数时间才成立。但内层循环的时间随 i 增长（log i），因此总时间必然超过线性。
• 如果是 O(log n)：只有单层对数循环才可能达成，而这里外层循环本身是线性的。

---

5. 递推公式法（递归算法）

示例7：斐波那契数列递归

c复制代码

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

• 递推公式：
  T(n) = T(n-1) + T(n-2) + O(1)
  （递归树展开后近似为指数级）
• 时间复杂度：O(2ⁿ)（实际为黄金分割比 O(φⁿ), φ≈1.618）

6. 冒泡排序

int x = 0;
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= n - i; j++) {
        x++;
    }
}

步骤解析

1. 外层循环：变量 i 从 1 到 n-1（因为条件是 i < n），共执行 n-1 次。

2. 内层循环：变量 j 的终止条件是 j <= n-i。每次外层循环的 i 值不同，内层循环的次数为：

   • 当 i=1 时，内层循环执行 n-1 次；
   • 当 i=2 时，内层循环执行 n-2 次；
   • ...
   • 当 i=n-1 时，内层循环执行 1 次。

3. 总操作次数：内层循环的总次数为等差数列求和：

   (n−1)+(n−2)+⋯+1=(n−1)⋅n2(n−1)+(n−2)+⋯+1=2(n−1)⋅n​

   即 n(n-1)/2。

4. 时间复杂度：忽略常数和低阶项后，结果为 O(n²)。

---

数学验证

总操作次数公式化简：
n(n−1)2=n2−n2  ⟹  O(n2)2n(n−1)​=2n2−n​⟹O(n2)

---

结论

无论输入规模如何增长，算法的执行时间与输入规模的平方成正比，因此时间复杂度为 O(n²)。

 

---

6. 常见循环模式总结

循环模式	循环次数公式	时间复杂度
for(i=0; i<n; i++)	n次	O(n)
for(i=1; i<n; i*=2)	log₂n次	O(log n)
for(i=0; i<n; i++) { for(j=0; j<m; j++) }	n×m次	O(nm)
for(i=0; i<n; i++) { for(j=0; j<i; j++) }	n(n-1)/2次	O(n²)
for(i=1; i<=n; i*=3)	log₃n次	O(log n)

---

7. 实战练习

分析以下代码的循环次数和时间复杂度：

c复制代码

void complex_loop(int n) {
    int count = 0;
    for(int i=1; i<=n; i++) {         // 外层循环
        for(int j=1; j<=i; j*=2) {    // 内层循环1（对数级）
            count++;
        }
        for(int k=0; k<i; k++) {      // 内层循环2（线性级）
            count++;
        }
    }
}

分步分析：

1. 外层循环：执行n次（i从1到n）。
2. 内层循环1（对数级）：
   • 当i=1时执行1次（j=1）
   • 当i=2时执行2次（j=1,2）
   • 当i=4时执行3次（j=1,2,4）
   • 总次数 = Σ_{i=1}^n (log₂i + 1) ≈ n log n
3. 内层循环2（线性级）：
   • 总次数 = Σ_{i=1}^n i = n(n+1)/2 ≈ O(n²)
4. 总时间复杂度：O(n log n) + O(n²) → O(n²)（保留最高阶项）

---

8. 注意事项

• 严格判断终止条件：注意是否包含等于号（如i <=n vs i <n）。
• 循环变量更新方式：i++（线性） vs i*=2（对数） vs i+=3（线性）。
• 嵌套循环的依赖关系：内层循环是否依赖外层变量（如示例4）。
• 递归算法的展开：通过递归树或递推公式计算调用次数。