埃拉托斯特尼筛法算法的时间复杂度

来自 维基百科:

算法的复杂性是 O(n(logn)(loglogn))位操作。

你是怎么知道的？

复杂性包括 loglogn术语，这告诉我在某个地方有一个 sqrt(n)。

假设我在前100个数字(n = 100)上运行筛选器，假设将数字标记为 Composite 需要固定的时间(数组实现) ，那么我们使用 mark_composite()的次数类似于

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

为了找到下一个质数(例如，在划掉所有 5的倍数后跳到 7) ，操作的次数应该是 O(n)。

复杂度是 O(n^3).你同意吗？

59716 次浏览
小开
最佳答案

  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(n2) 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.

小开

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

Keep in mind that when you find a prime number P while sieving, you don't start crossing off numbers at your current position + P; you actually start crossing off numbers at P^2. All multiples of P less than P^2 will have been crossed off by previous prime numbers.

小开
  1. The inner loop does n/i steps, where i is prime => the whole complexity is sum(n/i) = n * sum(1/i). According to prime harmonic series, the sum (1/i) where i is prime is log (log n). In total, O(n*log(log n)).
  2. I think the upper loop can be optimized by replacing n with sqrt(n) so overall time complexity will O(sqrt(n)loglog(n)):
void isPrime(int n){
int prime[n],i,j,count1=0;
for(i=0; i < n; i++){
prime[i] = 1;
}
prime[0] = prime[1] = 0;
for(i=2; i <= n; i++){
if(prime[i] == 1){
printf("%d ",i);
for(j=2; (i*j) <= n; j++)
prime[i*j] = 0;
}
}
}
小开

see take the above explanation the inner loop is harmonic sum of all prime numbers up to sqrt(n). So, the actual complexity of is O(sqrt(n)*log(log(sqrt(n))))

小开 
int n = 100;
int[] arr = new int[n+1];
for(int i=2;i<Math.sqrt(n)+1;i++) {
if(arr[i] == 0) {
int maxJ = (n/i) + 1;
for(int j=2;j<maxJ;j++)
{
arr[i*j]= 1;
}
}
}
for(int i=2;i<=n;i++) {
if(arr[i]==0) {
System.out.println(i);
}
}

For all i>2, Ti = sqrt(i) * (n/i) => Tk = sqrt(k) * (n/k) => Tk = n/sqrt(k)

Loop stops when k=sqrt(n) => n[ 1/sqrt(2) + 1/sqrt(3) + ...] = n * log(log(n)) => O(nloglogn)


提交答案