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

96

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?

Lazer
źródło
5
Nie wiem o reszcie (zbyt matowe jak na mój zbyt senny mózg), ale pierwiastek kwadratowy wynika z faktu, że jeśli liczba nie ma dzielników mniejszych niż pierwiastek kwadratowy, jest liczbą pierwszą. Dowiedziałem się również, że loglog (n) oznacza pierwiastek kwadratowy. Ładny.
R. Martinho Fernandes
13
W jaki sposób obecność loglog (n) oznacza, że ​​gdzieś jest sqrt (n)? (@Martinho: Dlaczego mówisz, że „właśnie się tego nauczyłeś”?) W rzeczywistości analiza nie obejmuje żadnych pierwiastków kwadratowych!
ShreevatsaR

Odpowiedzi:

121
  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 2 ) 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.

ShreevatsaR
źródło
Jeśli chodzi o część problemu, rozważasz asymptotyczną złożoność. Z drugiej strony rozważasz amortyzację. Jestem zmieszany.
crisron
2
@crisron Na czym polega problem? Nie jest tak, że „asymptotyczna złożoność” i „zamortyzowana złożoność” to dwa różne rodzaje tej samej rzeczy. Amortyzacja to tylko technika dokładniejszego liczenia czegoś, co może być asymptotyczną złożonością.
ShreevatsaR
Wszystko to, gdy myślałem o nich jako o innych. Dzięki za wyjaśnienie.
crisron
1
@ShreevatsaR Dlaczego obliczamy sumę szeregów harmonicznych do n terminów. Czy nie powinniśmy obliczać tylko do sqrt (n) wyrażeń? Podawanie odpowiedzi jako theta z n (loglogsqrt (n)) operacji arytmetycznych? Ponadto wikipedia mówi, że złożoność przestrzeni wynosi O (n). Czy nie powinno to być theta z n, ponieważ w każdym razie potrzebujemy tablicy n elementów?
a_123
@ s_123 Tak, możesz obliczyć tylko do √n składników, ale nie ma to znaczenia w analizie asymptotycznej (ani nawet znaczącej praktycznej różnicy w czasie wykonywania), ponieważ log (√x) = (1/2) log x dla dowolnego x. Więc Θ (n log log √n) = Θ (n log log n). Jeśli chodzi o twoje drugie pytanie, tak, złożoność przestrzeni to Θ (n), co również jest O (n): konwencjonalnie używa się O () do wskazania, że ​​określasz górną granicę, zamiast mówić Θ (), aby wskazać że jest to również dolna granica (zwłaszcza gdy dolna granica jest oczywista, tak jak tutaj).
ShreevatsaR
7

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.

jemfinch
źródło
10
stwierdzenie to jest prawdziwe samo w sobie, ale nie ma związku z przytoczonym stwierdzeniem, które samo w sobie nie ma wartości. Niezależnie od tego, czy zaczynamy od, pczy p^2, złożoność jest taka sama (z tablicami bezpośredniego dostępu). SUM (1/p) {p<N} ~ log (log N)Jest powodem.
Will Ness
6
  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 nsqrt(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;
            }
        }    
    }
    
Anand Tripathi
źródło
2
nie, zamiana n na sqrt (n) sprawia, że ​​jest to ~ n log log (sqrt n), co nadal jest ~ n log log n. i isprimejest to absolutnie niewłaściwa nazwa.
Will Ness,
-1

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

Bharath Kumar Reddy Appareddy
źródło
2
źle. zaznaczamy całą drogę do N: N / 2 + N / 3 + N / 5 + N / 7 + N / 11 + ... = N (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) ~ N log log (sqrt N) ~ N log log N.
Will Ness