algorithm - 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

其中 A 是一个 bool 数组，而 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))。因此，T(n) =\Theta(n\log(n))。 -n 对渐近计算成本没有任何影响，因为 n = o(n\log(n))。