n+n/2+n/3+...+n/n 之和的公式

Question

所以我得到了这个算法我需要计算它的时间复杂度

就像

for i=1 to n do
    k=i
    while (k<=n) do
        FLIP(A[k])
        k = k + i

whereA是一个布尔数组，FLIP 原样翻转当前值。因此它是O(1).

现在我明白应该调用内部 while 循环

n/1+n/2+n/3+...+n/n

如果我是对的，但是否有用于此类计算的公式？

这里很困惑

Answer 1

更精确的计算是T(n) \sum((n-i)/i)for i = 1 to n（因为k从 开始i）。因此，最终和n + n/2 + ... + n/n - n = n(1 + 1/2 + ... + 1/n) - n大约为 。我们知道1 + 1/2 + ... + 1/n = H(n)并且H(n) = \Theta(\log(n)). Hence, T(n) = \Theta(n\log(n))。在-n还没有对渐近computaional成本没有任何影响，因为n = o(n\log(n))。