Eratosthenes的Sievealgorithm的时间复杂度

维基百科：

该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) 

为了find下一个素数（例如在将所有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）：见谐波数 。 一个更合适的上界是n（1/2 + 1/3 + 1/5 + 1/7 + …），这是素数倒数n的和，即O（n log log n）。 （见这里或这里 ）

2. “find下一个素数”位只是整体O（n）， 分期付款 – 您将继续向前find下一个数字， 总共只有n次，而不是每步。 所以这个algorithm的整个部分只需要O（n）。

所以使用这两个函数可以得到O（n log log n）+ O（n）= O（n log log n）算术运算的上界。 如果你计算位操作，因为你要处理的数字是n，它们有大约log n位，这是log n的因子进来的地方，给出了O（n log n log n）位操作。

Answer 2

复杂性包括loglogn术语告诉我，有一个sqrt（n）的地方。

请记住，当您在筛选时发现素数P时，您不会在当前位置+ P处开始交叉数字; 你实际上开始在P^2交叉数字。 所有小于P^2的P倍数将被前面的素数所剔除。

Answer 3

1. 内部循环执行n/i步骤，其中i是素数=>整个复杂度是sum(n/i) = n * sum(1/i) 。 根据素数谐波序列，其中i是素数的sum (1/i)是log (log n) 。 总的来说， O(n*log(log n)) 。

2. 我认为可以通过用sqrt(n)replacen来优化上层循环，所以总的时间复杂度将会是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; } } }