请求分析内层步长为i的嵌套循环算法的时间复杂度

咱们来一步步拆解这个有点特殊的双层循环——内层循环的步长不是常规的1，而是外层循环的变量i，这是个很典型的时间复杂度分析案例。

首先看内层循环的执行次数：
对于外层循环的每一个i（从1到n），内层循环的j从1开始，每次增加i，直到j <= n。这个内层循环的执行次数其实就是n除以i的整数部分，也就是floor(n/i)。举几个具体例子：

• 当i=1时，j会遍历1到n的所有数，共n次；
• 当i=2时，j会取1、3、5…（或1、2+1、4+1…），总共约n/2次；
• 当i=n时，j只取1这一个值，共1次。

接下来计算总执行次数，就是把每个i对应的内层循环次数加起来：

总次数 = sum_{i=1到n} floor(n/i)

这个求和式的渐近复杂度可以用调和级数来推导：
这个求和式等价于n * (1 + 1/2 + 1/3 + ... + 1/n)，括号里的部分就是调和级数Hₙ，它的增长速度是对数级的，近似等于ln n + γ（γ是欧拉常数，约0.577）。所以总次数约等于n * ln n，对应的时间复杂度就是O(n log n)。

举个小例子验证：比如n=10，总次数是10+5+3+2+2+1+1+1+1+1=27，而10*ln10≈23，差距很小，完全符合对数增长的趋势。

总结一下：这个算法的时间复杂度是O(n log n)，核心原因是内层循环次数的求和对应调和级数，而调和级数的增长是对数级的，乘以n之后就得到了n log n的复杂度。

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