Złożoność czasowa algorytmu Sieve of Eratostenes

Z Wikipedii:

Złożoność algorytmu to O(n(logn)(loglogn))operacje bitowe.

Jak do tego doszedłeś?

To, że złożoność obejmuje ten loglogntermin, mówi mi, że sqrt(n)gdzieś jest.

Załóżmy, że uruchamiam sito na pierwszych 100 liczbach ( n = 100), zakładając, że oznaczenie liczb jako złożonych zajmuje stały czas (implementacja tablicy), liczba razy, której użyjemy, mark_composite()byłaby podobna

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

Aby znaleźć następną liczbę pierwszą (na przykład do przeskoczenia 7po przekreśleniu wszystkich liczb, które są wielokrotnościami 5), liczba operacji wyniosłaby O(n).

Więc złożoność byłaby O(n^3). Czy sie zgadzasz?

1. Twoje n / 2 + n / 3 + n / 5 +… n / 97 nie jest O (n), ponieważ liczba wyrazów nie jest stała. [Edytuj po edycji: O (n ² ) jest zbyt luźne, górna granica]. Luźna górna granica to n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (suma odwrotności wszystkich liczb do n), czyli O (n log n): patrz Liczba harmoniczna . Bardziej odpowiednią górną granicą jest n (1/2 + 1/3 + 1/5 + 1/7 +…), czyli suma odwrotności liczb pierwszych do n, czyli O (n log log n). (Zobacz tutaj lub tutaj .)

2. Bit „znajdź następną liczbę pierwszą” to tylko O ​​(n) ogółem, amortyzowany - przejdziesz dalej, aby znaleźć następną liczbę w sumie tylko n razy , a nie na krok. Więc cała ta część algorytmu zajmuje tylko O ​​(n).

Więc używając tych dwóch, otrzymujesz górną granicę O (n log log n) + O (n) = O (n log log n) operacji arytmetycznych. Jeśli liczysz operacje bitowe, ponieważ masz do czynienia z liczbami do n, mają one około log n bitów, czyli tam, gdzie pojawia się współczynnik log n, dając O (n log n log n) operacji bitowych.

To, że złożoność obejmuje termin loglogn, mówi mi, że gdzieś istnieje sqrt (n).

Pamiętaj, że kiedy znajdziesz liczbę pierwszą Ppodczas przesiewania, nie zaczynasz wykreślać liczb na swojej aktualnej pozycji + P; faktycznie zaczynasz wykreślać liczby od P^2. Wszystkie wielokrotności Pmniejsze niż P^2zostaną skreślone przez poprzednie liczby pierwsze.

1. Pętla wewnętrzna wykonuje n/ikroki, gdzie ijest pierwsza => cała złożoność jest sum(n/i) = n * sum(1/i). Zgodnie z szeregiem pierwszych harmonicznych, sum (1/i)gdzie ijest liczba pierwsza log (log n). W sumie O(n*log(log n)).

2. Myślę, że górną pętlę można zoptymalizować, zastępując nją sqrt(n)tak, aby ogólna złożoność czasowa 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;
           }
       }    
   }
   

patrz, weź powyższe wyjaśnienie, pętla wewnętrzna jest harmoniczną sumą wszystkich liczb pierwszych do sqrt (n). Tak więc rzeczywista złożoność wynosi O (sqrt (n) * log (log (sqrt (n))))