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) / 2 . Które patrząc na to wydaje się intuicyjne.
Stwierdzono jednak, że (n 2 + n) / 2 zachowuje się jak n 2, gdy n jest duże. W tym samym akapicie stwierdza on (n 2 + n) / 2 zachowuje się również podobnie jak n 2 / 2 . Używa go do sklasyfikowania powyższego algorytmu jako O (n 2 ) .
Uzyskać to (n = 2 + N) / 2 jest podobna do n- 2 / 2 , ponieważ Procentowo, n ma większego znaczenia. Nie rozumiem, dlaczego (n 2 + n) / 2 i n 2 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 2 ) . Patrząc na tę wewnętrzną pętlę, powiedziałbym, że była to n 2 + n / 2
źródło
n
rozwojem zarówno funkcje „n ^ 2”, jak i twoja funkcja zachowują się podobnie, a ich tempo wzrostu jest stałe. Jeśli masz złożone wyrażenie, dominuje funkcja, która rośnie szybciej.Odpowiedzi:
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)/2
i podwajasz liczbę elementów, to stała2
nie wpływa na wydłużenie czasu wykonania, terminn
powoduje podwojenie czasu wykonania, a terminn^2
powoduje czterokrotny wzrost wykonania czas.Ponieważ
n^2
termin ma największy wkład, złożoność Big-O jestO(n^2)
.źródło
O(n * log n) = O(n)
, co nie jest prawdą.O(n * log n) = O(n)
. Myślę, że to daje dobre wytłumaczenie uzasadnienia definicji.Definicja jest taka
jeśli istnieje jakaś stała C> 0 taka, że dla wszystkich n większych niż niektóre n_0 mamy
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).
źródło
g
jest niezerowa, tak naprawdę nie jest potrzebna, ponieważ zawsze możesz zwiększyć stałą C, aby instrukcja była prawdziwa dla skończonych wielu pierwszych wartości n_0.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
2
tutaj).To zostawia cię z
O(n^2 + n)
.Teraz, dla rozsądnie dużego
n
produktu, tj.n * n
Będzie znacznie większy niż tylkon
, 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
n
stajesz się.źródło
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
Podobnie, gdy n wzrasta z 1 000 000 do 1 000 000 000
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.
źródło
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.
źródło
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)
źródło
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:
Lub spojrzeć na to z innej strony, mamy
f(n)×c
kilka sekund, a Ty możesz poprawić wydajność, zmniejszającc
, zmniejszającn
lub zmniejszającf
zwroty za danen
.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()
źródło
n
jest wystarczająco niski, Big-O nie ma znaczenia”.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.
źródło
Big-O polega na „jak skomplikowanym” algorytmie. Jeśli masz dwa algorytmy, a weźmie
n^2*k
sekund do uruchomienia, a druga zajmujen^2*j
sekundy, 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ćk
alboj
, ale zarówno z algorytmy te są bardzo powolne w porównaniu do algorytmu wymagającegon*m
uruchomienia. Nie ma znaczenia, jak małe są stałe,k
lubj
, dla wystarczająco dużego wejścia,n*m
algorytm zawsze wygrywa, nawet jeślim
jest dość duży.Więc wywołujemy dwa pierwsze algorytmy
O(n^2)
i nazywamy drugiO(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. :)źródło