时间复杂度分析

一层循环

一般步骤

  1. 列出 循环次数 t迭代变量 (通常为i,j) 之间的关系
  2. 写出循环终止条件
  3. 联立 1 2 两式解出 t 与 n 之间的关系

例1

1
2
for (int i = 0; i*i < n; i++)
// print("%d", i);

首先列出 循环趟数t 和 迭代变量i 之间的关系表,可以得到 i=ti = t 这个关系式

t 0 1 2 3 t
i 0 1 2 3 i

而循环终止条件为 i2ni^2\geq n ,则可以得到循环次数和n之间的方程 t2nt^2\geq n ,解出 tnt\geq \sqrt{n} ,消去常数即可得到时间复杂度为 T(n)=O(n)T(n)=O(\sqrt{n})

例2

1
2
for (int i = 1; i <= n; i *= 2)
// print("%d", i);

同样列出关系表

t 0 1 2 3 t
i 1 2 4 8 2t2^t
循环终止条件为 i>ni>n ,则有 2t>n2^t>n,解出 t>log2nt>\log_2{n},即时间复杂度为 T(n)=O(log2n)T(n)=O(\log_2n)

两层或多层循环

如果多层循环之间的迭代变量互不干扰,则多层循环可以直接分解为多个单层循环,因此,此类多层循环的时间复杂度为内外层时间复杂度的乘积,比如下面这个例子

1
2
3
for (int i = 0; i < n; i*=2)
for (int j = 1; j < n; j++)
// print("%d", arr[i][j]);

这个例子中外层循环时间复杂度为 O(log2n)O(\log_2n) ,内层循环为 O(n)O(n) ,则整个循环的时间复杂度为 O(nlog2n)O(n\log_2n)