Eratosthenes算法筛选的时间复杂度

Question

来自维基百科:

算法的复杂性是 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).你同意吗？

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. "查找下一个素数"位只有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)位操作.

Answer 2

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

请记住,当您P在筛选时找到素数时,您不会在当前位置开始交叉数字+ P; 你真的开始越过数字了P^2.所有P小于的倍数都P^2将被先前的素数划掉.

Answer 3

1. 内循环执行n/i步骤,其中iprime =>整个复杂性sum(n/i) = n * sum(1/i).根据素数谐波系列,素数在sum (1/i)哪里.总的来说,.ilog (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;
           }
       }    
   }