Sieve of Eratosthenes 알고리즘의 시간

Sieve of Eratosthenes 알고리즘의 시간

---

에서 위키 백과 :

알고리즘의 코드는 비트 연산 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). 동의하십니까?

---

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 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) 비트 연산을 제공합니다.

---

표준에 loglogn 용어가 포함되어있는 것은 sqrt (n) 어딘가에 있음을 알려줍니다.

P체질하는 동안 소수를 찾으면 현재 위치에서 숫자를 교차에서 시작하지 않습니다 P. + ; 실제로에서 숫자를 교차하기 시작 P^2합니다. P보다 작은 모든 배수는 P^2이전 소수에 의해 교차됩니다.

---

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;
           }
       }    
   }
   

---

위의 설명을 참조하십시오. 내부 루프는 sqrt (n)까지 모든 소수의 고조파입니다. 실제의 실제는 O (sqrt (n) * log (log (sqrt (n))))입니다.

참고 URL : https://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm