时间复杂度分析

概念讲解

常见时间复杂度

复杂度 名称 示例
O(1) 常数 数组访问
O(log n) 对数 二分查找
O(n) 线性 单层循环
O(n log n) 线性对数 归并排序
O(n²) 平方 双层循环
O(2^n) 指数 子集枚举
O(n!) 阶乘 全排列

分析方法

  1. 看循环： 嵌套循环相乘
  2. 看递归： 画递归树或用主定理
  3. 看调用： 累加各部分

主定理

对于 T(n)=aT(n/b)+O(nd)T(n) = aT(n/b) + O(n^d)：

  • 若 a<bda < b^d，则 T(n)=O(nd)T(n) = O(n^d)
  • 若 a=bda = b^d，则 T(n)=O(ndlog⁡n)T(n) = O(n^d \log n)
  • 若 a>bda > b^d，则 T(n)=O(nlog⁡ba)T(n) = O(n^{\log_b a})

考点分析

初赛考查方式

  1. 选择题： 复杂度判断
  2. 程序阅读： 计算执行次数
  3. 填空题： 复杂度分析

常见考点

  • 循环次数计算
  • 递归复杂度
  • 主定理应用

例题精讲

例题 1：循环复杂度

题目： 以下代码的时间复杂度？

123for (int i = 1; i <= n; i *= 2) {
    // O(1)
}

解答：

i 取值：1, 2, 4, 8, ..., 2^k ≤ n

循环次数 = log₂n，时间复杂度 O(log n)

例题 2：递归复杂度

题目： 以下代码的时间复杂度？

12345void f(int n) {
    if (n <= 1) return;
    f(n/2);
    f(n/2);
}

解答：

T(n)=2T(n/2)+O(1)T(n) = 2T(n/2) + O(1)

a=2,b=2,d=0a=2, b=2, d=0，a>bda > b^d

T(n)=O(nlog⁡22)=O(n)T(n) = O(n^{\log_2 2}) = O(n)

练习题

  1. 双层循环的时间复杂度是多少？
查看答案

O(n²)

12345for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1)
    }
}

外层循环 n 次，内层循环 n 次，总共 n × n = n² 次。

  1. 二分查找的时间复杂度是多少？
查看答案

O(log n)

每次将搜索范围缩小一半：

  • 第 1 次：n
  • 第 2 次：n/2
  • 第 3 次：n/4
  • ...
  • 第 k 次：n/2^k

当 n/2^k = 1 时结束，k = log₂n。

  1. 主定理的三种情况是什么？
查看答案

对于 T(n)=aT(n/b)+O(nd)T(n) = aT(n/b) + O(n^d)：

  1. 若 a<bda < b^d：T(n)=O(nd)T(n) = O(n^d)
  2. 若 a=bda = b^d：T(n)=O(ndlog⁡n)T(n) = O(n^d \log n)
  3. 若 a>bda > b^d：T(n)=O(nlog⁡ba)T(n) = O(n^{\log_b a})

其中 a 是子问题个数，b 是子问题规模缩小倍数，d 是合并复杂度指数。

易错点

⚠️ 注意：

  1. 时间复杂度是最坏情况
  2. 嵌套循环相乘，顺序循环取大
  3. 递归要用主定理或递归树
  4. 常数项和系数忽略