如何计算嵌套for循环的运行步数及theta时间复杂度？

第一步：验证外循环迭代次数 #

外循环的终止条件是i > 0，初始值为n，每次步长减4，我们可以按n除以4的余数分4种情况验证：

• 若n mod 4 = 0：i的取值为n, n-4, n-8, ...,4，执行完i=4的迭代后i变为0，退出循环，总迭代次数为n/4 = ceil(n/4)
• 若n mod 4 = 1：i的取值为n, n-4, ...,1，执行完i=1的迭代后i变为-3，退出循环，总迭代次数为(n-1)/4 +1 = (n+3)/4 = ceil(n/4)
• 若n mod 4 = 2：i的取值为n, n-4, ...,2，执行完i=2的迭代后i变为-2，退出循环，总迭代次数为(n-2)/4 +1 = (n+2)/4 = ceil(n/4)
• 若n mod 4 = 3：i的取值为n, n-4, ...,3，执行完i=3的迭代后i变为-1，退出循环，总迭代次数为(n-3)/4 +1 = (n+1)/4 = ceil(n/4)
  四种情况都符合「外循环迭代次数为ceil(n/4)」的结论。

第二步：计算总操作次数 #

内循环的终止条件是j <n，初始值为当前外循环的i，因此单次外循环对应的内循环迭代次数为n -i。
所有迭代的总操作次数为各次外循环的内循环次数之和：

外循环i的取值为n, n-4, n-8, ..., r（r为n mod4的结果，r=0时取4），因此求和式为：
sum = (n-n) + (n-(n-4)) + (n-(n-8)) + ... + (n-r)
化简后求和式为：0 +4 +8 + ... +4*(m-1)，其中m为外循环迭代次数ceil(n/4)。
这是首项为0、末项为4(m-1)、公差为4的等差数列求和，结果为：
sum = 2*m*(m-1)

第三步：推导Theta复杂度 #

根据上取整的性质，n/4 ≤ m ≤ n/4 +1，代入求和结果可得：

• 下界：sum ≥ 2*(n/4)*(n/4 -1) = n²/8 - n/2
• 上界：sum ≤ 2*(n/4 +1)*(n/4) = n²/8 +n/2
  上下界的最高次项均为n²，且系数为正的常数，因此该嵌套循环的时间复杂度为Θ(n²)。

这类问题的通用分析思路 #

• 先逐层拆解循环的变量取值规则，不要直接套公式，可以手动写出前3个、最后2个循环变量的取值，对应边界条件验证循环次数的结论是否正确
• 写出总操作次数的求和表达式后，对上取整/下取整可以用余数分类讨论，或者用上下界放缩，只要放缩后最高次项的量级不变，就不会影响Theta的结果
• 最终化简求和式的时候，只需要保留最高次项，低次项和常数系数都可以忽略，直接得到对应的复杂度量级

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