algorithm - Sieve of Eratosthenes 算法的时间复杂度

Question

来自 Wikipedia:

The complexity of the algorithm is O(n(logn)(loglogn)) bit operations.

你是如何做到这一点的？

复杂性包括 loglogn 项告诉我某处有一个 sqrt(n)。

---

假设我在前 100 个数字 (n = 100) 上运行筛选，假设将数字标记为复合需要常数时间(数组实现)，我们使用的次数 >mark_composite() 会像

n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n^2)                         

并且要找到下一个质数(例如在划掉所有 5 的倍数后跳转到 7)，操作次数为O(n)。

因此，复杂度为 O(n^3)。 你同意吗？

Answer 1

1. 您的 n/2 + n/3 + n/5 + … n/97 不是 O(n)，因为项数不是常数。 [编辑后编辑:O(n²) 的上限太宽松。] 宽松的上限是 n(1+1/2+1/3+1/4+1/5+1/6+…1/n)(所有 数的倒数之和，直到 n)，即 O(n log n):参见 Harmonic number .更合适的上限是 n(1/2 + 1/3 + 1/5 + 1/7 + …)，即直到 n 的素数的倒数之和，即 O(n log log n)。 (参见 here 或 here。)

2. “找到下一个质数”位总体上只有 O(n)，amortized — 您将继续前进以在总计 中查找下一个数字 n 次，而不是每一步。所以整个算法部分只需要 O(n)。

所以使用这两个你得到 O(n log log n) + O(n) = O(n log log n) 算术运算的上限。如果你计算位操作，因为你正在处理最多 n 的数字，它们大约有 log n 位，这是 log n 的因子进来的地方，给出 O(n log n log log n) 位操作。