渐近时间复杂度中两个级数的计算差异是什么？

嘿，这个问题抓得特别准——这俩级数看起来都是“越来越小的数加起来”，但本质上的增长逻辑完全不同，咱们掰开揉碎了说：

第一个级数：n + n/2 + n/3 + … + n/n #

先把n提出来，这个级数可以写成 n * (1 + 1/2 + 1/3 + … + 1/n)。括号里的部分就是调和级数，它的增长速度是对数级的——简单说，当n很大的时候，这个和大约等于 ln(n) + γ（γ是欧拉常数，约0.577，是个固定值）。

所以整个级数的总和就是 n*(lnn + 常数)，忽略常数项和系数之后，时间复杂度就是 O(nlogn)。你可以这么理解：虽然每一项都在变小，但变小的速度很慢（是1/k的速度），加起来的总和会跟着n的对数一起增长，再乘以n之后就是nlogn级的增长。

第二个级数：n + n/2 + n/4 + … + 1 #

这个是等比级数，每一项都是前一项的1/2。咱们用等比数列求和公式算一下：首项a₁=n，公比r=1/2，项数大概是 log₂n + 1（因为每次除以2，到1的时候大概要log₂n次）。

求和公式是 S = a₁*(1 - r^k)/(1 - r)，代入进去就是：
S = n*(1 - (1/2)^k)/(1 - 1/2) = 2n*(1 - 1/(2^k))

当n很大的时候，2^k 差不多等于n，所以 1/(2^k) 趋近于0，整个总和就趋近于2n——不管n多大，这个总和永远不会超过2n，是个和n线性相关的数。所以时间复杂度就是 O(n)。

核心差异总结 #

• 第一个级数的每一项是n除以线性增长的整数（1,2,3,...,n），加起来的总和是n乘以对数，增长更快；
• 第二个级数的每一项是n除以指数增长的整数（1,2,4,...,2^k），加起来的总和有个固定上限（2n），增长是线性的。

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