Big O Pytanie o algorytm o szybkości wzrostu (n ^ 2 + n) / 2

Zadaję to pytanie, ponieważ nie jestem pewien jednego aspektu dotyczącego dużej notacji O.

Korzystam z książki Franka Carrano , Struktury danych i abstrakcje z Javą . W rozdziale „Efektywność algorytmów” pokazuje następujący algorytm:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Początkowo opisuje ten algorytm jako mający tempo wzrostu ^{(n 2  + n)} / ₂ . Które patrząc na to wydaje się intuicyjne.

Stwierdzono jednak, że ^{(n 2  + n)} / ₂ zachowuje się jak n ^2, gdy n jest duże. W tym samym akapicie stwierdza on ^{(n 2  + n)} / ₂ zachowuje się również podobnie jak ^{n 2} / ₂ . Używa go do sklasyfikowania powyższego algorytmu jako O (n ² ) .

Uzyskać to ^{(n = 2  + N)} / ₂ jest podobna do ^{n- 2} / ₂ , ponieważ Procentowo, n ma większego znaczenia. Nie rozumiem, dlaczego ^{(n 2  + n)} / ₂ i n ² są podobne, gdy n jest duże.

Na przykład, jeśli n = 1 000 000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Ten ostatni wcale nie jest podobny. W rzeczywistości jest to oczywiście dwa razy więcej niż środek. Jak więc Frank Carrano może powiedzieć, że są do siebie podobni? Ponadto, w jaki sposób algorytm jest klasyfikowany jako O (n ² ) . Patrząc na tę wewnętrzną pętlę, powiedziałbym, że była to n ² + ⁿ / ₂

Podczas obliczania złożoności algorytmu Big-O pokazany jest czynnik, który w największym stopniu przyczynia się do wzrostu czasu wykonania, jeśli liczba elementów uruchamianych przez algorytm wzrasta.

Jeśli masz algorytm o złożoności (n^2 + n)/2i podwajasz liczbę elementów, to stała 2nie wpływa na wydłużenie czasu wykonania, termin npowoduje podwojenie czasu wykonania, a termin n^2powoduje czterokrotny wzrost wykonania czas.
Ponieważ n^2termin ma największy wkład, złożoność Big-O jest O(n^2).

Definicja jest taka

f(n) = O(g(n))

jeśli istnieje jakaś stała C> 0 taka, że ​​dla wszystkich n większych niż niektóre n_0 mamy

|f(n)| <= C * |g(n)|

Jest to wyraźnie prawdziwe dla f (n) = n ^ 2 ig (n) = 1/2 n ^ 2, gdzie stała C powinna wynosić 2. Łatwo też zauważyć, że jest to prawda dla f (n) = n ^ 2 ig (n) = 1/2 (n ^ 2 + n).

Mówiąc o złożoności, interesują Cię tylko zmiany współczynnika czasu oparte na liczbie elementów ( n).

Jako taki możesz usunąć dowolny stały czynnik (jak 2tutaj).

To zostawia cię z O(n^2 + n).

Teraz, dla rozsądnie dużego nproduktu, tj. n * nBędzie znacznie większy niż tylko n, co jest powodem, dla którego możesz również pominąć tę część, co naprawdę pozostawia Ci ostateczną złożoność O(n^2).

To prawda, w przypadku małych liczb będzie znacząca różnica, ale staje się ona bardziej marginalna, im większa nstajesz się.

Nie jest tak, że „(n² + n) / 2 zachowuje się jak n², gdy n jest duże”, to tak, że (n² + n) / 2 rośnie jak n² wraz ze wzrostem n .

Na przykład, gdy n wzrasta z 1000 do 1 000 000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Podobnie, gdy n wzrasta z 1 000 000 do 1 000 000 000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Rosną podobnie, na tym właśnie polega Big O Notation.

Jeśli narysujesz (n² + n) / 2 i n² / 2 na Wolfram Alpha , są one tak podobne, że trudno je rozróżnić za pomocą n = 100. Jeśli narysujesz wszystkie trzy na Wolfram Alpha , zobaczysz dwie linie oddzielone stałym współczynnikiem 2.

Wygląda na to, że musisz jeszcze trochę rozwinąć dużą notację O. Jak wygodna jest ta notacja, jest bardzo myląca ze względu na użycie znaku równości, który nie jest tutaj używany do oznaczenia równości funkcji.

Jak wiadomo, notacja ta wyraża asymptotyczne porównania funkcji, a zapisanie f = O (g) oznacza, że f (n) rośnie co najwyżej tak szybko, jak g (n), gdy n idzie w nieskończoność. Prostym sposobem na przetłumaczenie tego jest stwierdzenie, że funkcja f / g jest ograniczona. Ale oczywiście musimy zadbać o miejsca, w których g wynosi zero, i otrzymujemy bardziej niezawodną definicję, którą można przeczytać prawie wszędzie .

Notacje te okazują się bardzo wygodne w obliczeniach - dlatego są tak rozpowszechnione - ale należy się z nimi obchodzić ostrożnie, ponieważ znak równości, który tam widzimy, nie oznacza równości funkcji . To prawie tak, jakby powiedzieć, że 2 = 5 mod 3 nie oznacza, że 2 = 5, a jeśli lubisz algebrę, możesz naprawdę zrozumieć dużą notację O jako coś równego modulo.

Teraz, aby powrócić do konkretnego pytania, obliczenie kilku wartości liczbowych i ich porównanie jest całkowicie bezcelowe: bez względu na to, jak duży jest milion, nie uwzględnia zachowania asymptotycznego. Byłoby to bardziej przydatne do stosunku wykresu funkcji f (n) = N (N-1) / 2 i g (n) = n² - jednak w tym szczególnym przypadku można łatwo zauważyć, że f (n) / g (n) jest mniejsze niż 1/2, jeśli n> 0, co oznacza, że f = O (g) .

Aby lepiej zrozumieć notację, powinieneś

• Pracuj z czystą definicją, a nie rozmytym wrażeniem opartym na podobnych rzeczach - tak jak właśnie to doświadczyłeś, takie rozmyte wrażenie nie działa dobrze.

• Poświęć trochę czasu na szczegółowe wypracowanie przykładów. Jeśli wypracujesz zaledwie pięć przykładów w ciągu tygodnia, to wystarczy, aby zwiększyć twoją pewność siebie. To zdecydowanie wysiłek.

Algebraiczne dygresja Jeśli jest algebra wszystkich funkcji Ν → v i C podalgebrą ograniczonych funkcji, ponieważ funkcja f zestawu funkcji należących do O (f) jest C -submodule od A i zasady obliczeń na dużym Notacja O po prostu opisuje, jak A działa na tych submodułach. Zatem równość, którą widzimy, jest równością C- podmodułów A , jest to po prostu inny rodzaj modułu.

Myślę, że źle rozumiesz, co oznacza duża notacja O.

Kiedy zobaczysz O (N ^ 2), oznacza to po prostu: kiedy problem stanie się 10 razy większy, czas jego rozwiązania wyniesie: 10 ^ 2 = 100 razy większy.

Napiszmy 1000 i 10000 w twoim równaniu: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Tak więc, podczas gdy N jest 10 razy większy, rozwiązania stają się 100 razy większe. Dlatego zachowuje się: O (N ^ 2)

jeśli n było 1,000,000wtedy

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 co?

Chociaż złożoność pozwala nam przewidzieć rzeczywisty koszt (sekundy lub bajty w zależności od tego, czy mówimy o złożoności czasowej czy złożoności przestrzeni), nie daje nam ona liczby sekund ani żadnej innej konkretnej jednostki.

Daje nam to pewien stopień proporcji.

Jeśli algorytm musi zrobić coś n razy, to zajmie n² × c dla pewnej wartości c, czyli tyle, ile czasu zajmuje każda iteracja.

Jeśli algorytm musi zrobić coś n² ÷ 2 razy, to zajmie n² × c dla pewnej wartości c, która jest dwa razy dłuższa niż każda iteracja.

Tak czy inaczej, czas jest nadal proporcjonalny do n².

Te stałe czynniki nie są czymś, co możemy po prostu zignorować; w rzeczywistości możesz mieć przypadek, w którym algorytm o złożoności O (n²) działa lepiej niż jeden o złożoności O (n), ponieważ jeśli pracujemy nad niewielką liczbą elementów, wpływ czynników konsolidacyjnych jest większy i może pokonać inne obawy . (Rzeczywiście, nawet O (n!) Jest takie samo jak O (1) dla wystarczająco niskich wartości n).

Ale nie o tym mówi złożoność.

W praktyce istnieje kilka różnych sposobów poprawy wydajności algorytmu:

1. Popraw wydajność każdej iteracji: O (n²) nadal działa w n² × c sekundach, ale c jest mniejsze.
2. Zmniejsz liczbę zaobserwowanych przypadków: O (n²) nadal działa w n² × c sekundach, ale n jest mniejsze.
3. Zamień algorytm na taki, który ma takie same wyniki, ale o mniejszej złożoności: np. Jeśli moglibyśmy zmienić coś O (n²) na coś O (n log n), a tym samym zmienić z n² × c₀ sekund na (n log n) × c₁ sekund .

Lub spojrzeć na to z innej strony, mamy f(n)×ckilka sekund, a Ty możesz poprawić wydajność, zmniejszając c, zmniejszając nlub zmniejszając fzwroty za dane n.

Najpierw możemy to zrobić za pomocą mikrooperatorów wewnątrz pętli lub przy użyciu lepszego sprzętu. To zawsze da poprawę.

Drugą rzeczą, jaką możemy zrobić, może być identyfikacja przypadku, w którym możemy zewrzeć algorytm przed zbadaniem wszystkiego lub odfiltrować niektóre dane, które nie będą znaczące. Nie da to poprawy, jeśli koszt zrobienia tego przewyższy zysk, ale ogólnie będzie to większa poprawa niż w pierwszym przypadku, szczególnie przy dużej n.

Trzeci możemy zrobić, używając całkowicie innego algorytmu. Klasycznym przykładem byłoby zastąpienie sortowania bąbelkowego szybkim sortowaniem. Przy niskiej liczbie pierwiastków mogliśmy pogorszyć sytuację (jeśli c₁ jest większe niż c₀), ale generalnie pozwala to na największe zyski, szczególnie przy bardzo dużych n.

W praktyce miary złożoności pozwalają nam rozumować różnice między algorytmami właśnie dlatego, że ignorują kwestię, w jaki sposób pomoże redukcja n lub c, i koncentrują się na badaniu f()

Czynnik stały

Punktem dużej notacji O jest to, że można wybrać dowolnie duży stały współczynnik, aby O (funkcja (n)) była zawsze większa niż funkcja C * (n). Jeśli algorytm A jest miliard razy wolniejszy niż algorytm B, wówczas mają tę samą złożoność O, o ile różnica ta nie rośnie, gdy n dowolnie rośnie.

Załóżmy, że ilustruje to stały współczynnik 1000000 - jest milion razy większy niż jest to konieczne, ale ilustruje to, że uważa się je za nieistotne.

(n ^ 2 + n) / 2 ”pasuje do„ O (n ^ 2), ponieważ dla dowolnego n, nie ważne jak duże, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 „nie pasuje” do mniejszego zestawu, np. O (n), ponieważ dla niektórych wartości (n ^ 2 + n) / 2> 1000000 * n.

Stałe czynniki mogą być dowolnie duże - algorytm z czasem działania n lat ma złożoność O (n), która jest „lepsza” niż algorytm z czasem działania n * log (n) mikrosekund.

Big-O polega na „jak skomplikowanym” algorytmie. Jeśli masz dwa algorytmy, a weźmie n^2*ksekund do uruchomienia, a druga zajmuje n^2*jsekundy, aby uruchomić, można argumentować, o który z nich jest lepszy, a może być w stanie zrobić kilka ciekawych optymalizacje próbować wpływać kalbo j, ale zarówno z algorytmy te są bardzo powolne w porównaniu do algorytmu wymagającego n*muruchomienia. Nie ma znaczenia, jak małe są stałe, klub j, dla wystarczająco dużego wejścia, n*malgorytm zawsze wygrywa, nawet jeśli mjest dość duży.

Więc wywołujemy dwa pierwsze algorytmy O(n^2)i nazywamy drugi O(n). Ładnie dzieli świat na klasy algorytmów. O to właśnie chodzi w big-O. To jak dzielenie pojazdów na samochody, ciężarówki i autobusy itp. Istnieje wiele różnic między samochodami i możesz spędzić cały dzień na kłótni, czy Prius jest lepszy niż Chevy Volt, ale pod koniec dnia, jeśli trzeba połączyć 12 osób w jedną, to jest to raczej bezsensowny argument. :)