求迭代器按自身对数增量增长的代码片段的大O时间复杂度

先看给定的代码片段：

i = 10
while(i < n) {
    i = i + log(i);
}

要分析这个循环的大O时间复杂度，核心是计算迭代次数：找到最小的k，使得经过k次迭代后i ≥ n。

分析过程 #

初始值i₀=10，每次迭代后i的更新规则是i_{m+1} = i_m + log(i_m)。当n足够大时，离散的迭代可以近似为连续函数的变化：把i看作迭代次数k的函数i(k)，则其瞬时变化率di/dk ≈ log(i)（每次增量log(i)对应连续情况下的变化率）。

分离变量后得到：
dk = di / log(i)

对这个式子从初始值10到n积分，总迭代次数k的近似值为：
k ≈ ∫₁₀ⁿ 1/log(x) dx

这个积分是对数积分函数li(n)减去li(10)，当n趋向于无穷大时，对数积分的渐近主导项是n/log(n)（低阶项和常数项在大O分析中可忽略）。

换个直观角度：循环结束时i的总增量约为n（初始值10相对于n可忽略），每次迭代的增量log(i)随i增大逐渐趋近于log(n)，平均增量的量级是log(n)，因此迭代次数的量级就是总增量除以平均增量，即n/log(n)。

结论 #

这个循环的时间复杂度是O(n / log n)。

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