Kompleksitas waktu algoritma Sieve of Eratosthenes

Dari Wikipedia:

Kompleksitas dari algoritma ini adalah O(n(logn)(loglogn))operasi bit.

Bagaimana Anda sampai pada hal itu?

Bahwa kompleksitas termasuk loglognistilah memberitahu saya bahwa ada suatu sqrt(n)tempat.

Misalkan saya menjalankan saringan pada 100 angka pertama ( n = 100), dengan asumsi bahwa menandai angka sebagai komposit membutuhkan waktu konstan (implementasi array), berapa kali yang kita gunakan mark_composite()akan menjadi seperti

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

Dan untuk menemukan bilangan prima berikutnya (misalnya melompat ke 7setelah mencoret semua bilangan yang merupakan kelipatannya 5), banyaknya operasinya adalah O(n).

Jadi, kerumitannya pasti O(n^3). Apa kamu setuju?

1. Anda n / 2 + n / 3 + n / 5 +… n / 97 bukanlah O (n), karena bilangan suku tidak konstan. [Edit setelah Anda edit: O (n ² ) terlalu longgar batas atasnya.] Batas atas longgar adalah n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (jumlah kebalikan dari semua bilangan hingga n), yaitu O (n log n): lihat bilangan Harmonic . Batas atas yang lebih tepat adalah n (1/2 + 1/3 + 1/5 + 1/7 +…), yaitu jumlah kebalikan dari bilangan prima hingga n, yaitu O (n log log n). (Lihat di sini atau di sini .)

2. Bit "temukan bilangan prima berikutnya" hanya O (n) secara keseluruhan, diamortisasi - Anda akan bergerak maju untuk mencari bilangan berikutnya hanya n kali total , bukan per langkah. Jadi seluruh bagian dari algoritma ini hanya membutuhkan O (n).

Jadi dengan menggunakan keduanya Anda mendapatkan batas atas O (n log log n) + O (n) = O (n log log n) operasi aritmatika. Jika Anda menghitung operasi bit, karena Anda berurusan dengan bilangan hingga n, operasi tersebut memiliki sekitar log n bit, yang mana faktor log n masuk, memberikan operasi bit O (n log n log log n).

Kompleksitas termasuk istilah loglogn memberi tahu saya bahwa ada akar persegi (n) di suatu tempat.

Ingatlah bahwa ketika Anda menemukan bilangan prima Psaat mengayak, Anda tidak mulai mencoret bilangan pada posisi Anda saat ini + P; Anda benar-benar mulai mencoret angka pada P^2. Semua kelipatan Pkurang dari P^2akan dicoret dengan bilangan prima sebelumnya.

1. Loop dalam melakukan n/ilangkah - langkah, di mana iadalah prime => seluruh kompleksitasnya sum(n/i) = n * sum(1/i). Menurut deret harmonik prima, sum (1/i)tempat iprima adalah log (log n). Secara total O(n*log(log n)),.

2. Saya pikir loop atas dapat dioptimalkan dengan mengganti ndengan sqrt(n)kompleksitas waktu secara keseluruhan akan 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;
           }
       }    
   }
   

lihat penjelasan di atas loop dalam adalah penjumlahan harmonis dari semua bilangan prima hingga akar (n). Jadi, kompleksitas sebenarnya adalah O (akar (n) * log (log (akar (n))))