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

16

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

Andrew S.
źródło
Jeśli jesteś zainteresowany, udzieliłem odpowiedzi na trzy zagnieżdżone pętle z zaznaczeniem drzewa wykonawczego . Układanka związana z zagnieżdżonymi pętlami
Grijesh Chauhan
1
w zasadzie chodzi o to, że wraz z nrozwojem 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.
AK_
1
@MichaelT: Nie sądzę, że jest to duplikat tego pytania, ponieważ drugie jest jedynie błędnym liczeniem. To jest bardziej subtelne pytanie, dlaczego pomniejsze terminy (w szczególności stałe mnożniki i wielomiany niższego stopnia) są ignorowane. Pytający tutaj najwyraźniej już rozumie kwestię poruszoną w drugim pytaniu, a odpowiedź, która jest wystarczająca na to pytanie, nie odpowie na to pytanie.
sdenham

Odpowiedzi:

38

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

Bart van Ingen Schenau
źródło
2
Podoba mi się, robi się trochę jaśniej.
Andrew S,
7
Jest to bardzo falista ręka. Może to być prawda lub fałsz. Jeśli możesz wziąć niewielką ilość matematyki, zobacz jedną z poniższych odpowiedzi.
usr
3
To rozumowanie jest zbyt niejasne: oznaczałoby, że moglibyśmy dojść do wniosku O(n * log n) = O(n), co nie jest prawdą.
por.
To może nie być najdokładniejsza odpowiedź lub najbardziej poprawna semantycznie, ale ważne jest to, że doprowadziło mnie to do zrozumienia centralnego punktu i myślę, że taki był cel autora. Jest to celowo niejasne, ponieważ szczegóły często odwracają uwagę od podstawowych zasad. Ważne jest, aby zobaczyć drewno drzew.
Andrew S,
Bart naprawdę mówił o terminach, a nie o czynnikach. Rozumiejąc to, nie możemy tego wywnioskować O(n * log n) = O(n). Myślę, że to daje dobre wytłumaczenie uzasadnienia definicji.
Mark Foskey
10

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

por
źródło
4
„Jeśli istnieje jakaś stała C> 0 taka, że ​​dla wszystkich n,” powinna być „Jeśli istnieją pewne stałe C, n_0 takie, że dla wszystkich n> n_0”
Taemyr
@Taemyr: Dopóki funkcja gjest 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.
por.
Nie, dopóki patrzymy na funkcje, nie ma skończonej liczby potencjalnych wartości n_0.
Taemyr
@Taemyr: n_0 jest liczbą skończoną. Wybierz C = max {f (i) / g (i): i = 1, ..., n_0}, a wtedy instrukcja będzie zawsze zawierać pierwsze wartości n_0, co możesz łatwo sprawdzić.
por.
W CS jest to mniej ważne, ponieważ n jest zwykle wielkością wejściową, a zatem dyskretną. W takim przypadku można wybrać C tak, aby n_0 = 1 działało. Ale formalna definicja jest większa niż jakiś próg, co eliminuje wiele drobiazgów w stosowaniu definicji.
Taemyr
6

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

Mario
źródło
Jak duże musi być n, aby różnica stała się marginalna? Ponadto, dlaczego usunięto / 2, jego istnienie zmniejsza o połowę wartość?
Andrew S,
6
@AndrewS Ponieważ Big O Notation mówi o wzroście. Dzielenie przez 2 nie ma znaczenia poza kontekstem testów porównawczych i znaczników czasu, ponieważ ostatecznie nie zmienia tempa wzrostu. Największy komponent ma jednak i to wszystko, co zatrzymujesz.
Neil,
2
@Niel, genialne, tak jasne. Chciałbym, żeby książki tak to ułożyły. Czasami myślę, że autorzy wiedzą za dużo, że zapominają, że zwykli śmiertelnicy nie mają swojej wiedzy funkcjonalnej, a zatem nie robią jasnych ważnych uwag, ale zamiast tego pochowają ją w jakimś formalnym opisie matematycznym lub pomijają wszystko razem, wierząc, że jest to dorozumiane.
Andrew S,
Chciałbym móc głosować tę odpowiedź więcej niż raz! @Neil, powinieneś pisać książki Big O.
Tersozaury
3

Nie jest tak, że „(n² + n) / 2 zachowuje się jak n², gdy n jest duże”, to tak, że (n² + n) / 2 rośnie jakwraz 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.

ShadSterling
źródło
To dobrze, to dla mnie bardzo wyraźnie. Dzięki za odpowiedź.
Andrew S
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.

Michael Le Barbier Grünewald
źródło
1
Ten artykuł z Wikipedii jest trudny do naśladowania po pierwszym małym kawałku. Został napisany dla utalentowanych matematyków przez wybitnego matematyka i nie jest rodzajem tekstu wprowadzającego, jakiego oczekiwałbym od encyklopedycznego artykułu. Dzięki za wgląd, choć wszystko jest w porządku.
Andrew S,
Przeceniasz poziom w tekście Wikipedii! :) Na pewno nie jest tak dobrze napisane. Graham, Knuth i Patashnik napisali uroczą książkę „Konkretna matematyka” dla studentów CS. Możesz także wypróbować „Sztukę programowania komputerowego” lub książkę z teorią liczb napisaną w latach 50. (Hardy i Wright, Rose), ponieważ zwykle są one skierowane do uczniów szkół średnich. Nie musisz czytać pełnej książki, jeśli ją wybierzesz, tylko część o asymptozie! Ale zanim zdecydujesz, ile musisz zrozumieć. :)
Michael Le Barbier Grünewald
1

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)

Pieter B.
źródło
1

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

Jon Hanna
źródło
„O (n!) Jest takie samo jak O (1) dla wystarczająco niskich wartości n” jest po prostu błędne. Musi istnieć lepszy sposób na wyjaśnienie, że „gdy njest wystarczająco niski, Big-O nie ma znaczenia”.
Ben Voigt
@BenVoigt Jeszcze nie spotkałem kogoś z takim samym retorycznym skutkiem, jak to miało miejsce, gdy go przeczytałem; nie jest pierwotnie mój, ukradłem go Ericowi Lippertowi, który mógł go stworzyć lub odebrać komuś innemu. Oczywiście odnosi się do żartów, takich jak „π równa się 3 dla małych wartości π i dużych wartości 3”, które są jeszcze starsze.
Jon Hanna
0

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.

Piotr jest
źródło
0

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

Jason Walton
źródło