如何计算给定嵌套循环代码的时间复杂度及解决内层循环问题

时间复杂度用大O记号表示算法运行时间随输入规模增长的渐近趋势，计算时只保留最高增长阶项，忽略所有常数系数、低阶项，核心规则如下：

• 常数次执行的操作，无论常数是50还是10000，复杂度都记为O(1)，不影响整体增长趋势
• 串行执行的代码段，总复杂度取各段复杂度的最高阶即可
• 嵌套循环的复杂度不能直接默认是各层最大迭代次数的乘积，如果内层循环迭代次数和外层变量相关，需要对所有外层取值对应的内层迭代次数做累加求和
• 求和时可以用已知的级数渐近结论简化计算：比如调和级数H_m = 1 + 1/2 + 1/3 + ... + 1/m的增长阶为Θ(log m)，等差数列求和为Θ(m²)，等比级数求和为Θ(最大项)

首先贴出待分析的代码：

def something(n):
   for i in range(50):
      for j in range(n//2):
         for k in range(n//(j+1)):
            do_constant_work()  # 单次执行为O(1)常数时间

我们从外到内逐层拆解：

1. 最外层i循环：固定迭代50次，迭代次数和输入n无关，属于常数项，最终计算时可以忽略系数影响。
2. 中间层j循环：迭代范围是0到n/2-1，总迭代次数和n线性相关，共n/2次。
3. 最内层k循环（即核心内层循环问题）：这层的迭代次数不是固定值，完全由当前外层j的取值决定：当j为0时，k迭代n次；j为1时，k迭代n/2次；j为2时，k迭代n/3次……当j取到n/2-1时，k仅迭代2次。
   这里要避开典型误区：不要直接把三层循环的最大迭代数相乘，算出50 * (n/2) * n = O(n²)的错误结论，因为k的迭代次数随j增大不断减小，必须做累加计算。

我们先计算单次i循环下，j、k两层的总操作次数：
把每个j对应的k循环次数累加，总次数为：
sum_{j=0}^{(n/2)-1} n/(j+1) = n * (1 + 1/2 + 1/3 + ... + 1/(n/2))
后面括号里的部分就是调和级数H_{n/2}，根据渐近性质，H_{n/2} ~ ln(n/2) + γ（γ为欧拉常数），增长阶为Θ(log n)，因此单次i循环下的总操作次数为n * Θ(log n) = Θ(n log n)。
再乘最外层的常数50，常数系数不影响大O阶，因此整段代码的时间复杂度为O(n log n)。

内层循环核心说明：内层循环的迭代次数和外层变量j成反比，j越大内层执行次数越少，累加后刚好被调和级数的log阶消去了一层n的增长，因此最终复杂度远低于直觉上三层循环算出的O(n²)结果。

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