时间复杂度分析
一层循环
一般步骤
- 列出 循环次数 t 和 迭代变量 (通常为i,j) 之间的关系
- 写出循环终止条件
- 联立 1 2 两式解出 t 与 n 之间的关系
例1
1 | for (int i = 0; i*i < n; i++) |
首先列出 循环趟数t 和 迭代变量i 之间的关系表,可以得到 这个关系式
t | 0 | 1 | 2 | 3 | … | t |
---|---|---|---|---|---|---|
i | 0 | 1 | 2 | 3 | … | i |
而循环终止条件为 ,则可以得到循环次数和n之间的方程 ,解出 ,消去常数即可得到时间复杂度为
例2
1 | for (int i = 1; i <= n; i *= 2) |
同样列出关系表
t | 0 | 1 | 2 | 3 | … | t |
---|---|---|---|---|---|---|
i | 1 | 2 | 4 | 8 | … | |
循环终止条件为 ,则有 ,解出 ,即时间复杂度为 |
两层或多层循环
如果多层循环之间的迭代变量互不干扰,则多层循环可以直接分解为多个单层循环,因此,此类多层循环的时间复杂度为内外层时间复杂度的乘积,比如下面这个例子
1 | for (int i = 0; i < n; i*=2) |
这个例子中外层循环时间复杂度为 ,内层循环为 ,则整个循环的时间复杂度为