时间复杂度分析 #

虽然代码千差万别，但常见的复杂度量级并不多。这些复杂度量级几乎涵盖了所有代码的复杂度量级。

复杂度量级可分为两类：多项式量级和非多项式量级。非多项式量级只有两个：O(2n) 和 O(n!)。

多项式量级（Polynomial Time）：时间复杂度可用多项式函数表示，即 O(n^k)

• 特点：问题规模增大时，复杂度增长相对缓慢，可高效处理大规模输入

非多项式量级（Non-Polynomial Time）：时间复杂度超过多项式函数增长速度

• 特点：复杂度随输入规模急剧增长，大规模问题不可行

当数据规模 n 增大时，非多项式量级算法的执行时间会急剧增加。因此，我们主要关注常见的多项式时间复杂度。

1. O(1) #

O(1) 表示常量级时间复杂度，不随 n 的增大而增长。例如：

int i = 8;
int j = 6;
int sum = i + j;

即使有 3 行代码，时间复杂度仍为 O(1)。只要算法中不存在循环、递归语句，时间复杂度就是 O(1)。

2. O(logn)、O(nlogn) #

O(logn) 示例：

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

变量 i 形成等比数列：1, 2, 4, 8, …, 2^x。当 2^x > n 时循环结束，即 x = log₂n。时间复杂度为 O(log₂n)。

对数底数统一表示：

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

时间复杂度为 O(log₃n)。由于对数转换公式 log₃n = log₃2 × log₂n，且大 O 表示可忽略常数系数，因此所有对数阶时间复杂度统一表示为 O(logn)。

O(nlogn)： O(logn) 代码执行 n 次，总时间复杂度为 O(nlogn)。这是归并排序、快速排序等高效排序算法的时间复杂度。

3. O(m+n)、O(m*n) #

当代码复杂度由两个数据规模决定时：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
 
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
 
  return sum_1 + sum_2;
}

由于无法评估 m 和 n 的量级大小，不能简单省略其中一个。时间复杂度为 O(m+n)。

加法法则修正： T1(m) + T2(n) = O(f(m) + g(n))
乘法法则： T1(m) × T2(n) = O(f(m) × f(n))

内容小结 #

复杂度分析用于评估算法执行效率与数据规模的增长关系。越高阶复杂度的算法，执行效率越低。

常见复杂度从低阶到高阶：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。几乎所有数据结构和算法的复杂度都在这个范围内。