algorithm - 我如何在少于 O(n) 的时间内计算总和 n+n/2+n/3+n/4........+(n/n)？

Question

我需要一个时间复杂度小于 O(n) 的算法。

目前我有这个算法：

int n; sum=n; for(int i=2;i<=n;i++) { sum+=n/i; }

Answer 1

那是 n * (1/1 + 1/2 + 1/3 + 1/4 + .. + 1/n)

后者的和是第n次谐波数，具有较好的近似性。

用 large 检查它n是否对你来说足够精确 - 显然，对于 small ns 只需使用你的“算法”或查找表。

import math

euler=0.5772156649015
sum=0
show=10
for i in range(1,1000001):
    sum += 1.0/i
    if i == show:
        approx = math.log(i) + euler + 1.0/(2*i)
        print "%7d %.2e" % (i, approx - sum)
        show *= 10

     10 8.33e-04
    100 8.33e-06
   1000 8.33e-08
  10000 8.33e-10
 100000 8.45e-12
1000000 9.93e-13