求和式n/1 + n/2 + … + n/n的时间复杂度是O(nlogn)还是O(n)

求和式复杂度结论 #

你提到的求和式 n/1 + n/2 + n/3 + … + n/n 的时间复杂度为 O(nlogn)，而非O(n)。

推导逻辑 #

该求和式可以变形为n乘以第n个调和数Hₙ：

Hₙ = 1 + 1/2 + 1/3 + … + 1/n
根据数学上的渐近分析，调和数的增长阶和自然对数一致，即Hₙ = ln n + γ + o(1)，其中γ为欧拉常数（约0.5772），是一个固定常量。代入求和式后整体的量级为nlnn，对应大O复杂度表示就是O(nlogn)*（算法复杂度分析中对数的底数不影响量级判断）。

对应筛法的复杂度说明 #

你采用的「遍历1~n的每个数，标记其所有倍数」的求约数方案，是经典的埃氏筛变种，总操作量和上述求和式完全匹配：

• 遍历数k时，需要标记的倍数数量为⌊n/k⌋
• 总操作数就是∑(k=1到n) ⌊n/k⌋，和你给出的求和式等价
  这个*O(nlogn)*的复杂度在实际场景中表现非常好，n到1e7量级都可以在普通设备上正常运行。

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