106

来自维基百科：

该算法的复杂性是 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)

并且要找到下一个素数（例如，7在删除所有 的倍数的数字后跳转到5），操作数将是O(n)。

因此，复杂性将是O(n^3)。你同意？

4

5 回答 5

132

  1. 您的 n/2 + n/3 + n/5 + … n/97 不是 O(n)，因为项数不是恒定的。[编辑后编辑：O(n 2 ) 的上限太松。] 松散的上限是 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)，摊销- 您将继续寻找下一个数字总共只有 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) 位操作。

于 2010-04-06T05:17:36.750 回答
8

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

请记住，当您P在筛选时找到质数时，您不会在当前位置开始划掉数字 + P；你实际上开始在 处划掉数字P^2。P所有小于的倍数都P^2将被先前的素数划掉。

于 2010-04-08T04:10:40.933 回答
6
  1. 内部循环执行n/i步骤，其中i素数 => 整个复杂度为sum(n/i) = n * sum(1/i). 根据素数调和级数，素数的sum (1/i)哪里i是log (log n)。总的来说，O(n*log(log n))。
  2. 我认为可以通过替换来优化上部循环n，sqrt(n)因此整体时间复杂度将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;
        }
    }    
}
于 2015-08-16T16:34:03.807 回答
1 
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);
  }
}

对于所有 i>2，Ti = sqrt(i) * (n/i) => Tk = sqrt(k) * (n/k) => Tk = n/sqrt(k)

当 k=sqrt(n) => n[ 1/sqrt(2) + 1/sqrt(3) + ...] = n * log(log(n)) => O(nloglogn) 时循环停止

于 2021-06-05T14:22:16.797 回答
-2

参见上面的解释，内部循环是直到 sqrt(n) 的所有素数的谐波和。所以，实际复杂度是 O(sqrt(n)*log(log(sqrt(n))))

于 2018-07-08T10:38:38.167 回答