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

96

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

121

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

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

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

— 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