埃拉托色尼筛算法的时间复杂度 [英] Time complexity of Sieve of Eratosthenes algorithm

问题描述

来自维基百科:

<块引用>

算法的复杂度为O(n(logn)(loglogn)) 位操作.

你是如何得出这个结论的?

包含 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).你同意吗?

解决方案

1. 你的 n/2 + n/3 + n/5 + ... n/97 不是 O(n)，因为项数不是常数. 松散的上限是 n(1+1/2+1/3+1/4+1/5+1/6+…1/n)(所有数到n的倒数之和)，即O(n log n):见谐波数.一个更合适的上限是 n(1/2 + 1/3 + 1/5 + 1/7 + …)，它是直到 n 的素数倒数之和，也就是 O(n log log n).(请参阅此处或此处.)

2. 找到下一个质数"位总体上只有 O(n)，摊销 — 您将继续查找 total 中的下一个数字，而不是每一步.所以整个算法部分只需要 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) 位操作.

From Wikipedia:

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

How do you arrive at that?

That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere.

---

Suppose I am running the sieve on the first 100 numbers (n = 100), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite() would be something like

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

And to find the next prime number (for example to jump to 7 after crossing out all the numbers that are multiples of 5), the number of operations would be O(n).

So, the complexity would be O(n^3). Do you agree?

解决方案

1. Your n/2 + n/3 + n/5 + … n/97 is not O(n), because the number of terms is not constant. [Edit after your edit: O(n²) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is sum of reciprocals of primes up to n, which is O(n log log n). (See here or here.)

2. The "find the next prime number" bit is only O(n) overall, amortized — you will move ahead to find the next number only n times in total, not per step. So this whole part of the algorithm takes only O(n).

So using these two you get an upper bound of O(n log log n) + O(n) = O(n log log n) arithmetic operations. If you count bit operations, since you're dealing with numbers up to n, they have about log n bits, which is where the factor of log n comes in, giving O(n log n log log n) bit operations.

这篇关于埃拉托色尼筛算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！