时间复杂度分析

一层循环

一般步骤

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

例1

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

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

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

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

例2

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

同样列出关系表

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

两层或多层循环

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

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

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