algorithm - 复杂循环的大 O 表示法

Question

我猜不出这个循环的大 O 表示法。

for (int j = 2; j < N; j++) {
    for (int k = 2*j; k <= N; k += j) {
        nums[k] = false;
    }
}

如何计算这个循环的算法复杂度？

Answer 1

这样做的诀窍是微积分用我们理解的积分代替总和。

for y from 2 to N:
    do roughly N/j things

所以我们有一个总和:

N/2 + N/3 + N/4 + ... + N/N
    = N (1/2 + 1/3 + 1/4 + ... + 1/N)

这个和可以用 1/x 的 1 到 N 的积​​分来近似。其积分为 log(x)。因此，模数误差需要 O(N log(N)) 步骤。

我使劲挥了挥手。但我向你保证，严格的细节是可以填写的，“用近似积分代替总和”有一个O(1)的错误。