时间复杂度计算

时间复杂度计算#

一层循环#

解题思路#

1. 列出循环趟数t以及每次循环i的变化值
2. 找到t和i的关系
3. 确定循环的停止条件
4. 联立两式,解方程
5. 得到t的表达式,去掉常数项和低阶项,得到时间复杂度

例题#

例题1#

例题2#

二层循环#

解题思路#

1. 列出外层循环趟数i的变化值
2. 列出内层循环语句的运行次数
3. 求和,得到总的运行次数
4. 去掉常数项和低阶项,得到时间复杂度

例题#

例题1#

例题2#

多层循环#

解题思路#

方法一(抽象为计算三维空间的体积)#

1. 1 层循环 → 算长度（1 维）
2. 2 层循环 → 算面积（2 维）
3. 3 层循环 → 算体积（3 维）
4. k 层循环 → 算k 维超体积

for(i=1; i<=n; i++)
    for(j=1; j<=i; j++)
        for(k=1; k<=j; k++)
            count++;

1. 该段三层循环代码可抽象为三维空间，其中i、j、k分别对应空间内三个维度的坐标轴。
2. 由循环约束条件 1 ≤ k ≤ j ≤ i ≤ n，在三维坐标系中围成的几何图形为四面体。
3. 四面体通用体积公式：$V=\dfrac{1}{6} \times 长 \times 宽 \times 高$，代入最大范围$n$，可得循环执行总次数近似为 $\boldsymbol{\dfrac{1}{6}n^3}$。
4. 时间复杂度计算规则为舍去常数项与低阶项，仅保留最高次幂，最终得出该代码时间复杂度为 $\boldsymbol{O(n^3)}$。