起始索引递增嵌套循环的时间复杂度计算及步长乘3场景求解

通用推导思路 #

针对起始索引/步长/终止条件随外层循环变化的嵌套循环，不要直接套用“内外层次数相乘”的简单规则，按以下步骤推导即可避免出错：

• 先确定外层循环的变量变化规则：明确外层迭代变量的取值范围、每次迭代的变化规律，先圈定外层的总迭代次数量级
• 固定外层迭代的变量值（比如设当前外层变量为i），单独计算该次外层迭代下内层循环的运行次数
• 对所有外层迭代对应的内层次数做求和，再对求和式做渐近分析，忽略常数系数和低阶项后得到最终时间复杂度

避坑提示：只有内层循环的运行次数完全和外层变量无关时，才能直接用内外层次数相乘，否则必须先求和再算渐近界。

变体问题计算 #

你给出的内层循环代码为 for j in range(1, (n**3) + 1, i * 3)，我们默认匹配这类题的常规外层逻辑：外层循环为 for i in range(1, n+1)，和下方附图的原题逻辑一致：

当修改为内层起始索引固定为1，每次迭代步长乘3（即j的更新逻辑为j *= 3，而非固定步长）时，推导过程如下：

1. 外层循环i从1到n，总迭代次数为O(n)
2. 对任意i，内层循环j从1开始，每次乘3，直到超过n³停止，内层的迭代次数满足 3^k ≤ n³，解得k ≤ log₃(n³) = 3log₃n，即内层单次运行次数为O(logn)
3. 总操作数为n * O(logn) = O(nlogn)，即该变体的时间复杂度为O(nlogn)

如果是你给出的代码场景：内层步长固定为3i，起始为1，终止为n³：

1. 对每个i，内层迭代次数约为 n³/(3i)，量级为O(n³/i)
2. 总操作数为求和（i从1到n）O(n³/i) = n³ * 求和（i从1到n）1/i
3. 调和级数求和1/i从1到n的量级为O(logn)，因此总时间复杂度为O(n³logn)

内容的提问来源于stack exchange，提问作者tomer shavit