Wolałbym jak najmniej formalnej definicji i prostej matematyki.

Szybka uwaga, jest to prawie na pewno mylące notację Big O (która jest górną granicą) z notacją Theta „Θ” (która jest dwiema stronami). Z mojego doświadczenia wynika, że ​​tak naprawdę jest to typowe dla dyskusji w środowiskach pozaakademickich. Przepraszamy za wszelkie nieporozumienia.

Za pomocą tego wykresu można wizualizować dużą złożoność O:

Najprostsza definicja, jaką mogę podać dla notacji Big-O, jest następująca:

Notacja Big-O to względna reprezentacja złożoności algorytmu.

W tym zdaniu jest kilka ważnych i celowo wybranych słów:

• krewny: możesz porównywać tylko jabłka do jabłek. Nie można porównać algorytmu mnożenia arytmetycznego z algorytmem sortującym listę liczb całkowitych. Ale porównanie dwóch algorytmów do wykonywania operacji arytmetycznych (jedno mnożenie, jedno dodawanie) powie ci coś znaczącego;
• reprezentacja: Big-O (w najprostszej formie) redukuje porównanie algorytmów do jednej zmiennej. Ta zmienna jest wybierana na podstawie obserwacji lub założeń. Na przykład algorytmy sortowania są zwykle porównywane na podstawie operacji porównania (porównywanie dwóch węzłów w celu ustalenia ich względnego uporządkowania). Zakłada się, że porównanie jest drogie. Ale co, jeśli porównanie jest tanie, ale zamiana jest droga? Zmienia porównanie; i
• złożoność: jeśli posortowanie 10 000 elementów zajmuje mi sekundę, ile czasu zajmie mi posortowanie miliona? Złożoność w tym przypadku jest względną miarą w stosunku do czegoś innego.

Wróć i przeczytaj ponownie powyższe, gdy przeczytasz resztę.

Najlepszym przykładem Big-O, jaki mogę wymyślić, jest robienie arytmetyki. Weź dwie liczby (123456 i 789012). Podstawowe operacje arytmetyczne, których nauczyliśmy się w szkole, to:

• dodanie;
• odejmowanie;
• mnożenie; i
• podział.

Każda z nich jest operacją lub problemem. Metoda ich rozwiązywania nazywana jest algorytmem .

Dodawanie jest najprostsze. Wyrównujesz liczby w górę (po prawej) i dodajesz cyfry w kolumnie, pisząc w wyniku ostatnią liczbę tego dodania. Część dziesiątek tej liczby jest przenoszona do następnej kolumny.

Załóżmy, że dodanie tych liczb jest najdroższą operacją w tym algorytmie. Jest oczywiste, że aby dodać te dwie liczby razem, musimy dodać razem 6 cyfr (i być może mieć 7). Jeśli dodamy dwie liczby 100 cyfr razem, musimy zrobić 100 dodatków. Jeśli dodamy dwie liczby 10 000 cyfr, musimy dodać 10 000 dodatków.

Widzisz wzór? Złożoność (oznacza liczbę operacji) jest wprost proporcjonalna do liczby cyfr n w większej ilości. Nazywamy to O (n) lub złożonością liniową .

Odejmowanie jest podobne (z wyjątkiem tego, że może być konieczne pożyczenie zamiast przeniesienia).

Mnożenie jest inne. Uszereguj liczby w górę, weź pierwszą cyfrę w dolnym numerze i pomnóż ją kolejno z każdą cyfrą w górnym numerze i tak dalej przez każdą cyfrę. Aby pomnożyć nasze dwie 6-cyfrowe liczby, musimy wykonać 36 mnożenia. Być może będziemy musieli zrobić aż 10 lub 11 dodanych kolumn, aby również uzyskać wynik końcowy.

Jeśli mamy dwie liczby 100-cyfrowe, musimy wykonać 10 000 mnożenia i 200 dodatków. Dla dwóch milionów cyfr musimy wykonać jeden bilion (10 ¹² ) mnożeń i dwa miliony dodatków.

Gdy algorytm skaluje się z n- kwadratem , jest to O (n ² ) lub kwadratowa złożoność . To dobry moment na wprowadzenie kolejnej ważnej koncepcji:

Dbamy tylko o najbardziej znaczącą część złożoności.

Bystry mógł zdać sobie sprawę, że możemy wyrazić liczbę operacji jako: n ² + 2n. Ale jak widzieliśmy w naszym przykładzie z dwiema liczbami po milion cyfr, drugi termin (2n) staje się nieistotny (stanowi 0,0002% wszystkich operacji na tym etapie).

Można zauważyć, że przyjęliśmy tutaj najgorszy scenariusz. Podczas mnożenia liczb 6-cyfrowych, jeśli jedna z nich ma 4 cyfry, a druga ma 6 cyfr, to mamy tylko 24 mnożenia. Mimo to obliczamy najgorszy scenariusz dla tego „n”, tj. Gdy oba są liczbami 6-cyfrowymi. Stąd notacja Big-O dotyczy scenariusza najgorszego przypadku algorytmu.

Książka telefoniczna

Kolejnym najlepszym przykładem, jaki mogę wymyślić, jest książka telefoniczna, zwykle nazywana Białą Stroną lub podobną, ale różni się w zależności od kraju. Ale mówię o tym, który wymienia ludzi według nazwiska, a następnie inicjałów lub imienia, ewentualnie adresu, a następnie numerów telefonów.

Co byś zrobił, gdybyś polecił komputerowi wyszukać numer telefonu „John Smith” w książce telefonicznej zawierającej 1 000 000 nazwisk? Ignorując fakt, że możesz zgadywać, jak daleko zaczęło się S (załóżmy, że nie możesz), co byś zrobił?

Typową implementacją może być otwarcie do połowy, zdobycie 500 000 ^tys i porównanie z „Smith”. Jeśli zdarzy się, że to „Smith, John”, po prostu będziemy mieli naprawdę szczęście. O wiele bardziej prawdopodobne jest, że „John Smith” będzie przed tym imieniem lub po nim. Jeśli to nastąpi, podzielimy ostatnią połowę książki telefonicznej na pół i powtórzmy. Jeśli jest to wcześniej, dzielimy pierwszą połowę książki telefonicznej na pół i powtarzamy. I tak dalej.

Nazywa się to wyszukiwaniem binarnym i jest używane każdego dnia w programowaniu, niezależnie od tego, czy zdajesz sobie z tego sprawę, czy nie.

Jeśli więc chcesz znaleźć nazwisko w książce telefonicznej zawierającej milion nazwisk, możesz znaleźć dowolne imię, robiąc to maksymalnie 20 razy. Porównując algorytmy wyszukiwania, decydujemy, że to porównanie jest naszym „n”.

• W przypadku książki telefonicznej o 3 nazwach potrzeba 2 porównań (maksymalnie).
• Na 7 potrzeba co najwyżej 3.
• Na 15 potrzeba 4.
• …
• Na 1 000 000 potrzeba 20.

To zdumiewająco dobre, prawda?

W kategoriach Big-O jest to O (log n) lub złożoność logarytmiczna . Teraz logarytm, o którym mowa, może być ln (podstawa e), log ₁₀ , log ₂ lub inna podstawa. Nie ma znaczenia, że ​​nadal jest to O (log n), podobnie jak O (2n ² ) i O (100n ² ) to wciąż oba O (n ² ).

Warto w tym miejscu wyjaśnić, że Big O można wykorzystać do określenia trzech przypadków za pomocą algorytmu:

• Najlepszy przypadek: w wyszukiwaniu książki telefonicznej najlepszym przypadkiem jest znalezienie nazwy w jednym porównaniu. Jest to O (1) lub stała złożoność ;
• Oczekiwany przypadek: Jak omówiono powyżej, jest to O (log n); i
• Najgorszy przypadek: jest to również O (log n).

Zwykle nie dbamy o najlepszy przypadek. Interesuje nas oczekiwany i najgorszy przypadek. Czasami jedno lub drugie będzie ważniejsze.

Powrót do książki telefonicznej.

Co jeśli masz numer telefonu i chcesz znaleźć nazwisko? Policja ma odwrotną książkę telefoniczną, ale takich wyszukiwań odmawia się opinii publicznej. Albo czy oni? Technicznie możesz odwrócić wyszukiwanie numeru w zwykłej książce telefonicznej. W jaki sposób?

Zaczynasz od imienia i porównujesz liczbę. Jeśli to pasuje, świetnie, jeśli nie, przechodzisz do następnego. Musisz to zrobić w ten sposób, ponieważ książka telefoniczna jest nieuporządkowana (w każdym razie według numeru telefonu).

Aby znaleźć nazwę nadaną numerowi telefonu (wyszukiwanie wsteczne):

• Najlepszy przypadek: O (1);
• Oczekiwany przypadek: O (n) (dla 500 000); i
• Najgorszy przypadek: O (n) (dla 1 000 000).

Podróżujący sprzedawca

Jest to dość znany problem w informatyce i zasługuje na wzmiankę. W tym problemie masz N miast. Każde z tych miast jest połączone z 1 lub więcej innymi miastami drogą o określonej odległości. Problemem podróżującego sprzedawcy jest znalezienie najkrótszej trasy, która odwiedza każde miasto.

Brzmi prosto? Pomyśl jeszcze raz.

Jeśli masz 3 miasta A, B i C z drogami między wszystkimi parami, możesz przejść:

• A → B → C
• A → C → B
• B → C → A
• B → A → C.
• C → A → B
• C → B → A

Cóż, w rzeczywistości jest ich mniej, ponieważ niektóre z nich są równoważne (A → B → C i C → B → A są równoważne, na przykład, ponieważ korzystają z tych samych dróg, na odwrót).

W rzeczywistości istnieją 3 możliwości.

• Zabierz to do 4 miast, a masz (iirc) 12 możliwości.
• Z 5 to 60.
• 6 staje się 360.

Jest to funkcja operacji matematycznej zwanej silnią . Gruntownie:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 ×… × 2 × 1 = 3,04140932 × 10 ⁶⁴

Tak więc Big-O problemu Podróżującego Sprzedawcy to O (n!) Lub złożoność czynnikowa lub kombinatoryczna .

Zanim dotrzesz do 200 miast, we wszechświecie nie ma już czasu na rozwiązanie problemu z tradycyjnymi komputerami.

Coś do przemyślenia.

Czas wielomianowy

Kolejną kwestią, o której chciałem szybko wspomnieć, jest to, że mówi się, że każdy algorytm, który ma złożoność O (n ^a ) , ma złożoność wielomianową lub że można go rozwiązać w czasie wielomianowym .

O (n), O (n ² ) itd. Są czasem wielomianowym. Niektórych problemów nie da się rozwiązać w czasie wielomianowym. Z tego powodu niektóre rzeczy są używane na świecie. Kryptografia klucza publicznego jest tego doskonałym przykładem. Trudno jest obliczyć dwa podstawowe czynniki bardzo dużej liczby. Gdyby tak nie było, nie moglibyśmy używać systemów kluczy publicznych, których używamy.

W każdym razie, to wszystko dla mojego (mam nadzieję, że po angielsku) wyjaśnienia Big O (poprawionego).

Pokazuje, jak algorytm skaluje się na podstawie wielkości wejściowej.

O (n ² ) : znany jako złożoność kwadratowa

• 1 element: 1 sekunda
• 10 pozycji: 100 sekund
• 100 przedmiotów: 10000 sekund

Zauważ, że liczba przedmiotów wzrasta 10-krotnie, ale czas zwiększa się 10-krotnie ² . Zasadniczo n = 10, a więc O (n ² ) daje nam współczynnik skalowania n ^2, który wynosi 10 ² .

O (n) : znany jako złożoność liniowa

• 1 element: 1 sekunda
• 10 pozycji: 10 sekund
• 100 elementów: 100 sekund

Tym razem liczba przedmiotów wzrasta 10-krotnie, podobnie jak czas. n = 10, a zatem współczynnik skalowania O (n) wynosi 10.

O (1) : znany jako stała złożoność

• 1 element: 1 sekunda
• 10 pozycji: 1 sekunda
• 100 elementów: 1 sekunda

Liczba przedmiotów wciąż rośnie 10-krotnie, ale współczynnik skalowania O (1) wynosi zawsze 1.

O (log n) : znany jako złożoność logarytmiczna

• 1 element: 1 sekunda
• 10 elementów: 2 sekundy
• 100 elementów: 3 sekundy
• 1000 przedmiotów: 4 sekundy
• 10000 przedmiotów: 5 sekund

Liczba obliczeń jest zwiększana tylko o dziennik wartości wejściowej. Zatem w tym przypadku, zakładając, że każde obliczenie zajmuje 1 sekundę, dziennik danych wejściowych njest wymaganym czasem, a zatem log n.

To jest sedno tego. Zmniejszają matematykę, więc może to nie być dokładnie n ² lub cokolwiek, co mówią, ale to będzie dominujący czynnik w skalowaniu.

Notacja Big-O (zwana również notacją „asymptotycznego wzrostu”) to, jak funkcje „wyglądają”, gdy ignoruje się stałe czynniki i rzeczy w pobliżu źródła . Używamy go, aby mówić o skali rzeczy .

Podstawy

dla „dostatecznie” dużych nakładów ...

• f(x) ∈ O(upperbound)oznacza f„rośnie nie szybciej niż”upperbound
• f(x) ∈ Ɵ(justlikethis)znaczy f„rośnie dokładnie jak”justlikethis
• f(x) ∈ Ω(lowerbound)oznacza f„nie rośnie wolniej niż”lowerbound

notacja big-O nie dba o stałe czynniki: 9x²mówi się, że funkcja „rośnie dokładnie tak jak” 10x². Notacja asymptotyczna big-O nie obchodzi też rzeczy niesymptotycznych („rzeczy blisko źródła” lub „co się dzieje, gdy rozmiar problemu jest niewielki”): 10x²mówi się, że funkcja „rośnie dokładnie tak jak” 10x² - x + 2.

Dlaczego chcesz ignorować mniejsze części równania? Ponieważ stają się one całkowicie przyćmione przez duże części równania, gdy rozważasz coraz większą skalę; ich wkład staje się karłowaty i nieistotny. (Patrz sekcja przykładowa.)

Innymi słowy, chodzi o stosunek, gdy idziesz do nieskończoności. Jeśli podzielisz rzeczywisty czas potrzebny na to O(...), otrzymasz stały czynnik w limicie dużych nakładów. Intuicyjnie ma to sens: funkcje „skalują się”, jeśli można pomnożyć jeden, aby uzyskać drugi. Wtedy mówimy ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... oznacza to, że dla „wystarczająco dużego” rozmiaru problemu N (jeśli zignorujemy rzeczy w pobliżu źródła), istnieje pewna stała (np. 2,5, całkowicie wymyślona) taka, że:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Istnieje wiele możliwości wyboru stałej; często „najlepszy” wybór jest znany jako „stały współczynnik” algorytmu ... ale często go ignorujemy, tak jak ignorujemy nie większe terminy (zobacz sekcję Czynniki stałe, aby dowiedzieć się, dlaczego zwykle nie mają znaczenia). Możesz również pomyśleć o powyższym równaniu jako ograniczeniu, mówiąc: „ W najgorszym przypadku czas, który to zajmie, nigdy nie będzie gorszy niż w przybliżeniu N*log(N), w granicach 2,5 (stałego współczynnika, na którym nam nie zależy). ” .

Ogólnie O(...)jest najbardziej przydatny, ponieważ często dbamy o zachowanie w najgorszym przypadku. Jeśli f(x)reprezentuje coś „złego”, jak użycie procesora lub pamięci, wówczas „ f(x) ∈ O(upperbound)” oznacza „ upperboundjest najgorszym scenariuszem użycia procesora / pamięci”.

Aplikacje

Jako czysto matematyczna konstrukcja notacja wielkiej litery O nie ogranicza się do mówienia o czasie przetwarzania i pamięci. Możesz go użyć do omówienia asymptotyków wszystkiego, co ma znaczenie skalowanie, takich jak:

• liczba możliwych uścisków dłoni wśród Nosób na imprezie ( Ɵ(N²)w szczególności N(N-1)/2, ale ważne jest to, że „skaluje się jak”N² )
• probabilistyczna oczekiwana liczba osób, które widziały marketing wirusowy w funkcji czasu
• w jaki sposób opóźnienie witryny zmienia się wraz z liczbą jednostek przetwarzających w CPU, GPU lub klastrze komputerowym
• jak skala mocy cieplnej na procesorze umiera w zależności od liczby tranzystorów, napięcia itp.
• ile czasu potrzebuje algorytm do uruchomienia, w zależności od wielkości wejściowej
• ile miejsca potrzebuje algorytm, w zależności od wielkości wejściowej

Przykład

W powyższym przykładzie uścisku dłoni wszyscy w pokoju podają sobie rękę. W tym przykładzie #handshakes ∈ Ɵ(N²). Dlaczego?

Cofnij się trochę: liczba uścisków dłoni to dokładnie n-wybierz-2 lub N*(N-1)/2(każda z N osób podaje ręce N-1 innym osobom, ale to podwójnie liczy uściski dłoni, więc podziel przez 2):

Jednak w przypadku bardzo dużej liczby osób pojęcie liniowe Njest karłowate i skutecznie przyczynia się do stosunku 0 (na wykresie: ułamek pustych pól na przekątnej w stosunku do wszystkich pól maleje wraz ze wzrostem liczby uczestników). Dlatego skalowanie jest takie order N², że liczba uścisków dłoni „rośnie jak N²”.

#handshakes(N)
────────────── ≈ 1/2
     N²

To tak, jakby pustych pól na przekątnej wykresu (N * (N-1) / 2 znaczniki wyboru) nie było nawet (N ² znaczników asymptotycznie).

(tymczasowa dygresja od „zwykłego angielskiego” :) Jeśli chcesz to sobie udowodnić, możesz wykonać prostą algebrę na stosunku, aby podzielić go na wiele terminów ( limoznacza „rozważany na granicy”, po prostu zignoruj ​​go, jeśli nie widziałem tego, to po prostu notacja dla „a N jest naprawdę bardzo duży”):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Liczba uścisków dłoni „wygląda tak jak” x2 dla dużych wartości, że jeśli zapisalibyśmy stosunek # handshakes / x², to fakt, że nie potrzebujemy dokładnie x² uścisków dłoni, nawet by się nie pokazał w systemie dziesiętnym przez dowolnie dużą chwilę.

np. dla x = 1 milion, stosunek # uścisk dłoni / x²: 0,499999 ...

Intuicja budynku

To pozwala nam składać takie oświadczenia, jak ...

„Wystarczająco dużej inputsize = N, bez względu na to, co jest czynnikiem stałym, jeśli podwoi wielkość wejściową ...

• ... podwajam czas potrzebny algorytmowi O (N) („czas liniowy”). ”

  N → (2N) = 2 ( N )

• ... podwoiłem kwadrat (czterokrotnie) czas potrzebny algorytmowi O (N²) („czas kwadratowy”). ” (Np. Problem 100x większy zajmuje 100² = 10000x tak długo ... być może nie do utrzymania)

  N² → (2N) ² = 4 ( N² )

• ... podwoiłam (octuple) czas potrzebny algorytmowi O (N³) („czas sześcienny”). ” (Np. Problem 100x tak duży zajmuje 100³ = 1000000x tak długo ... bardzo niezrównoważony)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... Dodaję stałą ilość czasu, jaki zajmuje algorytm O (log (N)) („czas logarytmiczny”). ” (Tanio!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (stała ilość) + ( c log (N) )

• ... Nie zmieniam czasu, jaki zajmuje algorytm O (1) („czas stały”). ” (Najtańszy!)

  c * 1 → c * 1

• ... I „(w zasadzie) podwajam„ czas potrzebny algorytmowi O (N log (N)). ” (Dość często)

  jest mniejszy niż O (N ^1.000001 ), co możesz chcieć nazwać zasadniczo liniowym

• ... absurdalnie zwiększam czas potrzebny algorytmowi O (2 ^N ) („czas wykładniczy”). ” (Podwoiłbyś (lub potroiłeś itd.) Czas, zwiększając problem o jedną jednostkę)

  2 ^N → 2 ^2N = (4 ^N ) ........... inaczej: ... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[dla matematycznie nachylonych możesz najechać myszką na spoilery, by zobaczyć drobne sidenotes]

(dzięki kredytowi https://stackoverflow.com/a/487292/711085 )

(technicznie rzecz biorąc, stały czynnik może mieć znaczenie w niektórych bardziej ezoterycznych przykładach, ale sformułowałem rzeczy powyżej (np. w log (N)) tak, że nie ma)

Są to porządki wzrostu, które programiści i informatycy stosują jako punkty odniesienia. Cały czas to widzą. (Więc technicznie możesz pomyśleć: „Podwojenie danych wejściowych powoduje, że algorytm O (√N) 1,414 razy wolniej”, lepiej jest myśleć o nim jako „jest gorszy niż logarytmiczny, ale lepszy niż liniowy”.)

Czynniki stałe

Zwykle nie obchodzi nas, jakie są konkretne stałe czynniki, ponieważ nie wpływają one na wzrost funkcji. Na przykład dwa algorytmy mogą zająć trochę O(N)czasu, ale jeden może być dwa razy wolniejszy od drugiego. Zwykle nie przejmujemy się zbytnio, chyba że czynnik jest bardzo duży, ponieważ optymalizacja to trudny biznes ( kiedy optymalizacja jest przedwczesna? ); również samo wybranie algorytmu z lepszym big-O często poprawia wydajność o rzędy wielkości.

Niektóre asymptotycznie lepsze algorytmy (np. O(N log(log(N)))Sortowanie nieporównywalne) mogą mieć tak duży stały współczynnik (np. 100000*N log(log(N))) Lub narzut, który jest stosunkowo duży jak O(N log(log(N)))w przypadku ukrytego + 100*N, że rzadko warto ich używać nawet w przypadku „dużych zbiorów danych”.

Dlaczego O (N) jest czasem najlepsze, co możesz zrobić, tj. Dlaczego potrzebujemy struktur danych

O(N)algorytmy są w pewnym sensie „najlepszymi” algorytmami, jeśli chcesz odczytać wszystkie swoje dane. Sam akt odczytu szeregu danych jest O(N)operacją. Ładowanie go do pamięci jest zwykle O(N)(lub szybsze, jeśli masz wsparcie sprzętowe lub w ogóle nie ma czasu, jeśli już odczytałeś dane). Jednak jeśli dotkniesz lub nawet spojrzysz na każdą część danych (lub nawet każdą inną część danych), Twój algorytm zajmie trochę O(N)czasu, aby wykonać to wyszukiwanie. Bez względu na to, ile czasu zajmie faktyczny algorytm, będzie tak przynajmniej O(N)dlatego, że spędził ten czas na przeglądaniu wszystkich danych.

To samo można powiedzieć o samym akcie pisania . Wszystkie algorytmy, które wypisują N rzeczy, zajmą N czasu, ponieważ wynik jest co najmniej tak długi (np. Wydruk wszystkich permutacji (sposobów zmiany kolejności) zestawu N kart do gry jest silna:) O(N!).

To motywuje do użycia struktur danych : struktura danych wymaga odczytania danych tylko raz (zazwyczaj O(N)czas), a także pewnej ilości wstępnego przetwarzania (np. O(N)Lub O(N log(N))lub O(N²)), które staramy się zachować na małą skalę. Następnie modyfikowanie struktury danych (wstawianie / usuwanie / itp.) I wykonywanie zapytań dotyczących danych zajmuje bardzo mało czasu, takich jak O(1)lub O(log(N)). Następnie przystąp do wykonywania dużej liczby zapytań! Ogólnie rzecz biorąc, im więcej pracy wykonasz z wyprzedzeniem, tym mniej pracy będziesz musiał wykonać później.

Załóżmy na przykład, że posiadałeś współrzędne szerokości i długości geograficznej milionów odcinków drogi i chciałeś znaleźć wszystkie skrzyżowania.

• Naiwna metoda: jeśli posiadasz współrzędne skrzyżowania ulicy i chcesz zbadać pobliskie ulice, musisz za każdym razem przejść przez miliony segmentów i sprawdzić, czy nie ma sąsiedztwa.
• Gdybyś musiał to zrobić tylko raz, nie byłoby problemu z naiwną metodą O(N) pracy tylko raz, ale jeśli chcesz to zrobić wiele razy (w tym przypadku Nrazy, raz dla każdego segmentu), my musiałbym wykonać O(N²)pracę lub 1000000² = 1000000000000 operacji. Nie dobrze (nowoczesny komputer może wykonać około miliarda operacji na sekundę).
• Jeśli użyjemy prostej struktury zwanej tabelą skrótów (tablica szybkiego wyszukiwania, znana również jako mapa skrótów lub słownik), ponosimy niewielki koszt, przygotowując wszystko na O(N)czas. Następnie wyszukiwanie klucza według klucza zajmuje tylko stały czas (w tym przypadku naszym kluczem są współrzędne szerokości i długości geograficznej, zaokrąglone w siatkę; przeszukujemy sąsiednie przestrzenie siatki, których jest tylko 9, co jest stały).
• Nasze zadanie przeszło od niewykonalnego O(N²) do opanowania O(N), a wszystko, co musieliśmy zrobić, to zapłacić niewielki koszt, aby zrobić tablicę skrótów.
• analogia : analogią w tym konkretnym przypadku jest układanka: Stworzyliśmy strukturę danych, która wykorzystuje pewną właściwość danych. Jeśli nasze odcinki drogi są jak elementy układanki, grupujemy je według pasującego koloru i wzoru. Następnie wykorzystujemy to, aby uniknąć późniejszej dodatkowej pracy (porównywanie puzzli podobnego koloru ze sobą, a nie z każdym innym puzzlem).

Morał tej historii: struktura danych pozwala nam przyspieszyć operacje. Co więcej, zaawansowane struktury danych pozwalają łączyć, opóźniać, a nawet ignorować operacje w niewiarygodnie sprytny sposób. Różne problemy miałyby różne analogie, ale wszystkie obejmowałyby uporządkowanie danych w sposób wykorzystujący pewną strukturę, na której nam zależy, lub którą sztucznie nałożyliśmy na księgowość. Pracujemy z wyprzedzeniem (w zasadzie planujemy i organizujemy), a teraz powtarzane zadania są znacznie łatwiejsze!

Praktyczny przykład: wizualizacja rzędów wzrostu podczas kodowania

Notacja asymptotyczna jest zasadniczo oddzielna od programowania. Notacja asymptotyczna jest matematyczną strukturą do myślenia o tym, jak rzeczy się skalują i mogą być używane w wielu różnych dziedzinach. To powiedziawszy ... w ten sposób stosuje się asymptotyczną notację do kodowania.

Podstawy: za każdym razem, gdy wchodzimy w interakcję z każdym elementem w kolekcji o rozmiarze A (takim jak tablica, zestaw, wszystkie klucze mapy itp.) Lub wykonujemy iteracje pętli A, która jest multiplikatywnym czynnikiem wielkości A Dlaczego mówię „czynnik mnożący”? - ponieważ pętle i funkcje (prawie z definicji) mają multiplikatywny czas działania: liczba iteracji, czas pracy wykonanej w pętli (lub dla funkcji: liczba wywołań funkcja, czasy pracy wykonane w funkcji). (Dzieje się tak, jeśli nie robimy nic wymyślnego, takiego jak pomijanie pętli lub wcześniejsze wyjście z pętli, lub zmiana przepływu sterowania w funkcji na podstawie argumentów, co jest bardzo częste.) Oto kilka przykładów technik wizualizacji z towarzyszącym pseudokodem.

(tutaj xs oznaczają jednostki czasu pracy stałej, instrukcje procesora, kody interpretera, cokolwiek)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Przykład 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Przykład 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Jeśli zrobimy coś nieco skomplikowanego, nadal możesz sobie wyobrazić, co się dzieje:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Liczy się tutaj najmniejszy rozpoznawalny kontur, jaki można narysować; trójkąt ma kształt dwuwymiarowy (0,5 A ^ 2), podobnie jak kwadrat ma kształt dwuwymiarowy (A ^ 2); Stały współczynnik dwóch tutaj pozostaje w asymptotycznym stosunku między nimi, jednak ignorujemy to jak wszystkie czynniki ... (Istnieją pewne niefortunne niuanse w tej technice, której tu nie wchodzę; może cię wprowadzić w błąd).

Oczywiście nie oznacza to, że pętle i funkcje są złe; wręcz przeciwnie, są one elementami składowymi współczesnych języków programowania i my je kochamy. Widzimy jednak, że sposób, w jaki splatamy pętle oraz funkcje i warunki warunkowe wraz z naszymi danymi (przepływ sterujący itp.), Naśladuje wykorzystanie czasu i przestrzeni przez nasz program! Jeśli wykorzystanie czasu i przestrzeni stanie się problemem, wtedy uciekamy się do sprytu i znajdujemy prosty algorytm lub strukturę danych, których nie rozważaliśmy, aby w jakiś sposób zmniejszyć porządek wzrostu. Niemniej jednak te techniki wizualizacji (choć nie zawsze działają) mogą naiwnie zgadywać w najgorszym przypadku.

Oto kolejna rzecz, którą możemy rozpoznać wizualnie:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Możemy po prostu zmienić to i zobaczyć, że to O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

A może rejestrujesz (N) przebiegi danych, dla całkowitego czasu O (N * log (N)):

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Niepowiązany, ale warty wzmianki: jeśli wykonamy skrót (np. Wyszukiwanie słownika / tablicy mieszającej), jest to współczynnik O (1). To dość szybko.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Jeśli robimy coś bardzo skomplikowane, na przykład za pomocą funkcji rekurencyjnej lub algorytm dziel i zwyciężaj, można użyć Mistrza Twierdzenie (zazwyczaj działa), lub w śmiesznych przypadków Akra-Bazzi Twierdzenie (prawie zawsze działa) spojrzeć w górę czas działania twojego algorytmu na Wikipedii.

Ale programiści tak nie myślą, bo w końcu intuicja algorytmu staje się drugą naturą. Zaczniesz kodować coś nieefektywnego i od razu pomyślisz „czy robię coś rażąco nieefektywnego? ”. Jeśli odpowiedź brzmi „tak” ORAZ przewidujesz, że to naprawdę ma znaczenie, możesz cofnąć się o krok i pomyśleć o różnych sztuczkach, aby przyspieszyć bieg rzeczy (odpowiedź brzmi prawie zawsze: „użyj haszowania”, rzadko „użyj drzewa”, i bardzo rzadko coś nieco bardziej skomplikowanego).

Amortyzowana i średnia złożoność przypadków

Istnieje również koncepcja „zamortyzowanego” i / lub „przeciętnego przypadku” (zauważ, że są one różne).

Średnia wielkość liter : nie jest to nic więcej niż użycie notacji wielkiej-O dla oczekiwanej wartości funkcji, a nie samej funkcji. W zwykłym przypadku, w którym uważa się, że wszystkie dane wejściowe są równie prawdopodobne, średni przypadek jest tylko średnią czasu działania. Na przykład w przypadku Quicksort, nawet jeśli najgorszy przypadek dotyczy O(N^2)niektórych naprawdę złych danych wejściowych, średnia wielkość jest zwykle O(N log(N))(bardzo złe dane wejściowe są bardzo małe, więc jest ich tak mało, że nie zauważamy ich w średnim przypadku).

Amortyzowana metoda najgorszego przypadku : Niektóre struktury danych mogą mieć złożoność najgorszego przypadku, która jest duża, ale gwarantuj, że jeśli wykonasz wiele z tych operacji, średnia ilość pracy, którą wykonasz, będzie lepsza niż w najgorszym przypadku. Na przykład możesz mieć strukturę danych, która zwykle zajmuje stały O(1)czas. Czasami jednak „czknie” i zabiera trochę O(N)czasu na jedną losową operację, ponieważ być może trzeba wykonać księgowość, wyrzucanie elementów bezużytecznych lub coś w tym stylu ... ale obiecuje, że jeśli wystąpi czkawka, nie będzie czkawka więcej operacji. W najgorszym przypadku koszt przypada O(N)na operację, ale zamortyzowany koszt w wielu seriach wynosi O(N)/N=O(1)na operację. Ponieważ duże operacje są wystarczająco rzadkie, ogromną ilość okazjonalnej pracy można uznać za wtapiającą się w resztę pracy jako stały czynnik. Mówimy, że praca jest „amortyzowana” w przypadku wystarczająco dużej liczby połączeń, która znika asymptotycznie.

Analogia do analizy zamortyzowanej:

Jeździsz samochodem. Czasami musisz spędzić 10 minut na stacji benzynowej, a następnie spędzić 1 minutę na uzupełnianiu paliwa w zbiorniku. Jeśli robisz to za każdym razem, gdy jedziesz gdziekolwiek samochodem (spędzasz 10 minut jazdy na stacji benzynowej, spędzasz kilka sekund, napełniając ułamek galonu), byłoby to bardzo nieefektywne. Ale jeśli napełnisz zbiornik raz na kilka dni, 11 minut jazdy do stacji benzynowej zostanie „zamortyzowane” na wystarczająco dużej liczbie przejazdów, abyś mógł go zignorować i udawać, że wszystkie twoje podróże były może o 5% dłuższe.

Porównanie średniej i najgorszego zamortyzowanego przypadku:

• Przypadek średni: przyjmujemy pewne założenia dotyczące naszych danych wejściowych; tzn. jeśli nasze dane wejściowe mają różne prawdopodobieństwa, wówczas nasze dane wyjściowe / środowiska wykonawcze będą miały różne prawdopodobieństwa (z których bierzemy średnią). Zazwyczaj zakładamy, że wszystkie nasze dane wejściowe są jednakowo prawdopodobne (jednolite prawdopodobieństwo), ale jeśli dane wejściowe w świecie rzeczywistym nie pasują do naszych założeń dotyczących „średniej wartości wejściowej”, obliczenia średniej mocy wyjściowej / czasu działania mogą być bez znaczenia. Jeśli jednak spodziewasz się równomiernie losowych danych wejściowych, warto o tym pomyśleć!
• Amortyzowany najgorszy przypadek: jeśli używasz zamortyzowanej struktury danych najgorszego przypadku, wydajność jest gwarantowana w ramach zamortyzowanego najgorszego przypadku ... ostatecznie (nawet jeśli dane wejściowe są wybrane przez złego demona, który wie wszystko i próbuje spieprzyć cię). Zwykle używamy tego do analizy algorytmów, które mogą być bardzo „niestabilne” w działaniu z nieoczekiwanymi dużymi czkawkami, ale z czasem działają tak samo dobrze, jak inne algorytmy. (Jeśli jednak twoja struktura danych nie ma górnych limitów na wiele wybitnych zadań, na które jest skłonny się odkładać na później, złoczyńca może być może zmusi cię do nadrobienia maksymalnej ilości odkładanej pracy naraz.

Chociaż jeśli masz uzasadnione obawy o atakującego, istnieje wiele innych algorytmicznych wektorów ataku, o które należy się martwić oprócz amortyzacji i średniej wielkości przypadków.)

Zarówno średnie przypadki, jak i amortyzacja są niezwykle przydatnymi narzędziami do myślenia i projektowania z uwzględnieniem skalowania.

(Patrz Różnica między średnią analizą a analizą zamortyzowaną, jeśli zainteresowany jest tym podtematem.)

Wielowymiarowy big-O

Przez większość czasu ludzie nie zdają sobie sprawy, że w pracy jest więcej niż jedna zmienna. Na przykład w algorytmie wyszukiwania ciągów algorytm może zająć trochę czasu O([length of text] + [length of query]), tzn. Jest liniowy w dwóch podobnych zmiennych O(N+M). Inne bardziej naiwne algorytmy mogą być O([length of text]*[length of query])lub O(N*M). Ignorowanie wielu zmiennych jest jednym z najczęstszych niedopatrzeń, jakie widzę w analizie algorytmów, i może utrudniać projektowanie algorytmu.

Cała historia

Pamiętaj, że big-O to nie cała historia. Możesz drastycznie przyspieszyć niektóre algorytmy, używając buforowania, czyniąc je nieświadomymi dla pamięci podręcznej, unikając wąskich gardeł, pracując z RAM zamiast dysku, stosując równoległość lub wykonując pracę z wyprzedzeniem - techniki te są często niezależne od kolejności wzrostu notacja „duże-O”, choć często liczba rdzeni jest widoczna w notacji dużych-O algorytmów równoległych.

Pamiętaj również, że z powodu ukrytych ograniczeń programu, możesz nie przejmować się zachowaniem asymptotycznym. Być może pracujesz z ograniczoną liczbą wartości, na przykład:

• Jeśli sortujesz coś w rodzaju 5 elementów, nie chcesz używać szybkiego szybkiego O(N log(N))sortowania; chcesz użyć sortowania wstawiania, które sprawdza się przy małych nakładach. Takie sytuacje często pojawiają się w algorytmach „dziel i rządź”, w których dzielisz problem na coraz mniejsze podproblemy, takie jak sortowanie rekurencyjne, szybkie transformacje Fouriera lub mnożenie macierzy.
• Jeśli niektóre wartości są skutecznie ograniczone z powodu jakiegoś ukrytego faktu (np. Przeciętne ludzkie imię jest delikatnie ograniczone do około 40 liter, a wiek człowieka jest miękko ograniczony do około 150). Możesz także nałożyć granice na dane wejściowe, aby skutecznie uczynić warunki stałymi.

W praktyce, nawet wśród algorytmów, które mają taką samą lub podobną asymptotyczną wydajność, ich względna zasługa może faktycznie wynikać z innych czynników, takich jak: inne czynniki wydajności (oba są szybkie i sortowane O(N log(N)), ale szybki korzysta z pamięci podręcznej procesora); kwestie związane z brakiem wydajności, takie jak łatwość wdrożenia; czy biblioteka jest dostępna oraz jak godna zaufania i utrzymywana jest biblioteka.

Programy będą również działały wolniej na komputerze 500 MHz w porównaniu z komputerem 2 GHz. Tak naprawdę nie uważamy tego za część granic zasobów, ponieważ myślimy o skalowaniu w kategoriach zasobów maszynowych (np. Na cykl zegara), a nie na rzeczywistą sekundę. Istnieją jednak podobne rzeczy, które mogą „potajemnie” wpływać na wydajność, takie jak to, czy działasz w trybie emulacji, czy kod zoptymalizowany przez kompilator, czy nie. Może to spowodować, że niektóre podstawowe operacje potrwają dłużej (nawet względem siebie), a nawet przyspieszyć lub spowolnić niektóre operacje asymptotycznie (nawet względem siebie). Efekt może być mały lub duży między różnymi implementacjami i / lub środowiskiem. Czy zmieniasz języki lub maszyny, aby wykończyć tę dodatkową pracę? To zależy od stu innych powodów (konieczność, umiejętności, współpracownicy, wydajność programisty,

Powyższe kwestie, takie jak efekt wyboru używanego języka programowania, prawie nigdy nie są uważane za część stałego czynnika (ani nie powinny); należy jednak być ich świadomym, ponieważ czasami (choć rzadko) mogą one wpływać na różne rzeczy. Na przykład w cpython implementacja natywnej kolejki priorytetowej jest asymptotycznie nieoptymalna ( O(log(N))zamiast O(1)wyboru wstawiania lub znajdowania-min); korzystasz z innej implementacji? Prawdopodobnie nie, ponieważ implementacja C jest prawdopodobnie szybsza i prawdopodobnie istnieją inne podobne problemy gdzie indziej. Są kompromisy; czasami mają znaczenie, a czasem nie.

( edycja : Wyjaśnienie „zwykłego angielskiego” kończy się tutaj).

Dodatki matematyczne

Dla kompletności, dokładna definicja notacji big-O jest następująca: f(x) ∈ O(g(x))oznacza, że ​​„f jest asymptotycznie ograniczona przez const * g”: ignorując wszystko poniżej pewnej skończonej wartości x, istnieje stała taka, że |f(x)| ≤ const * |g(x)|. (Pozostałe symbole są następujące: podobnie jak Ooznacza ≤, Ωoznacza ≥. Istnieją warianty małych liter: ooznacza <, i ωoznacza>.) f(x) ∈ Ɵ(g(x))Oznacza zarówno, jak f(x) ∈ O(g(x))i f(x) ∈ Ω(g(x))(górną i dolną granicę g): istnieją pewne stałe takie, że f zawsze będzie leżeć w „paśmie” pomiędzy const1*g(x)i const2*g(x). Jest to najsilniejsze asymptotyczne stwierdzenie, które możesz z grubsza zrównać==. (Przepraszam, do tej pory postanowiłem opóźnić wzmiankę o symbolach wartości bezwzględnej, dla jasności; szczególnie dlatego, że nigdy nie widziałem wartości ujemnych pojawiających się w kontekście informatyki).

Ludzie często używają = O(...), co jest być może bardziej poprawną notacją „comp-sci” i jest całkowicie uzasadniona w użyciu; „f = O (...)” jest czytane „f jest porządkiem ... / f jest xxx ograniczone przez ...” i jest uważane za „f jest jakimś wyrażeniem, którego asymptotykami są ...”. Nauczono mnie używać bardziej rygorystycznych ∈ O(...). ∈oznacza „jest elementem” (nadal czytany jak poprzednio). W tym konkretnym przypadku, O(N²)zawiera elementy, takie jak { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} i jest nieskończenie duża, ale nadal jest to zestaw.

O i Ω nie są symetryczne (n = O (n²), ale n² nie jest O (n)), ale Ɵ jest symetryczne, a (ponieważ wszystkie te relacje są przechodnie i zwrotne) Ɵ jest zatem symetryczne, przechodnie i zwrotne , a zatem dzieli zestaw wszystkich funkcji na klasy równoważności . Klasa równoważności to zbiór rzeczy, które uważamy za takie same. To znaczy, biorąc pod uwagę dowolną funkcję, jaką możesz wymyślić, możesz znaleźć kanonicznego / unikalnego „asymptotycznego przedstawiciela” klasy (ogólnie biorąc limit ... myślę ); tak jak możesz zgrupować wszystkie liczby całkowite w kursach lub równaniach, możesz pogrupować wszystkie funkcje za pomocą Ɵ w x-ish, log (x) ^ 2-ish itp., po prostu ignorując mniejsze terminy (ale czasami możesz utknąć z bardziej skomplikowane funkcje, które są oddzielnymi klasami dla siebie).

=Notacja może być bardziej rozpowszechnione i stosowane nawet w dokumentach przez światowej sławy naukowców komputerowych. Ponadto często zdarza się, że w swobodnym otoczeniu ludzie mówią, O(...)kiedy mają na myśli Ɵ(...); jest to technicznie prawdą, ponieważ zbiór rzeczy Ɵ(exactlyThis)jest podzbiorem O(noGreaterThanThis)... i łatwiej jest pisać. ;-)

EDYCJA: Szybka uwaga, jest to prawie na pewno mylące notację Big O (która jest górną granicą) z notacją Theta (która jest zarówno górną, jak i dolną granicą). Z mojego doświadczenia wynika, że ​​jest to typowe dla dyskusji w środowiskach pozaakademickich. Przepraszamy za wszelkie nieporozumienia.

Jednym zdaniem: w miarę jak rośnie rozmiar pracy, ile czasu zajmuje jej wykonanie?

Oczywiście używa się tylko „rozmiaru” jako danych wejściowych i „czasu zajętego” jako danych wyjściowych - ten sam pomysł ma zastosowanie, jeśli chcesz rozmawiać o zużyciu pamięci itp.

Oto przykład, w którym mamy N T-shirty, które chcemy wysuszyć. Będziemy zakładać, że to niezwykle szybkie, aby je w pozycji suszenia (czyli interakcja człowiek jest znikoma). Oczywiście tak nie jest w prawdziwym życiu ...

• Korzystanie z linii do mycia na zewnątrz: zakładając, że masz nieskończenie duży ogród, pranie wysycha w czasie O (1). Niezależnie od tego, ile masz, będzie to samo słońce i świeże powietrze, więc rozmiar nie wpływa na czas schnięcia.

• Korzystanie z suszarki bębnowej: wkładasz 10 koszulek do każdego ładunku, a następnie są robione godzinę później. (Zignoruj ​​tutaj rzeczywiste liczby - nie mają one znaczenia). Zatem wysuszenie 50 koszul zajmuje około 5 razy więcej niż suszenie 10 koszul.

• Umieszczanie wszystkiego w przewiewnej szafce: jeśli umieścimy wszystko w jednym dużym stosie i po prostu pozwolimy na to ogólnemu ciepłu, wyschnie środkowe koszule. Nie chciałbym zgadywać szczegółów, ale podejrzewam, że jest to przynajmniej O (N ^ 2) - wraz ze wzrostem ładunku prania czas suszenia wydłuża się szybciej.

Jednym ważnym aspektem notacji „duże O” jest to, że nie mówi, który algorytm będzie szybszy dla danego rozmiaru. Weź tablicę hashtable (klucz ciągu, wartość całkowitą) vs tablicę par (ciąg, liczba całkowita). Czy szybciej jest znaleźć klucz w tablicy mieszającej lub element tablicy, oparty na łańcuchu? (tj. dla tablicy „znajdź pierwszy element, w którym część ciągu pasuje do podanego klucza.”) Tabele skrótów są na ogół amortyzowane (~ = „średnio”) O (1) - po ich skonfigurowaniu powinno to zająć około w tym samym czasie, aby znaleźć wpis w tabeli 100 wpisów, jak w tabeli 1 000 000 wpisów. Znalezienie elementu w tablicy (opartej raczej na treści niż indeksie) jest liniowe, tj. O (N) - średnio będziesz musiał spojrzeć na połowę pozycji.

Czy to sprawia, że ​​hashtable jest szybszy niż tablica do wyszukiwania? Niekoniecznie. Jeśli masz bardzo małą kolekcję wpisów, tablica może być szybsza - możesz być w stanie sprawdzić wszystkie ciągi w czasie potrzebnym do obliczenia kodu skrótu tego, na który patrzysz. Jednak w miarę powiększania się zestawu danych tablica mieszająca ostatecznie pokonuje tablicę.

Duże O opisuje górny limit zachowań funkcji, np. Czas działania programu, gdy dane wejściowe stają się duże.

Przykłady:

• O (n): Jeśli podwoję wielkość wejściową, środowisko wykonawcze podwaja się

• O (n ² ): Jeśli rozmiar wejściowy podwaja się, czas działania czterokrotnie

• O (log n): Jeśli rozmiar wejścia podwoi się, czas działania wzrośnie o jeden

• O (2 ⁿ ): Jeśli wielkość wejściowa wzrośnie o jeden, środowisko wykonawcze podwaja się

Rozmiar wejściowy jest zwykle przestrzenią w bitach potrzebną do przedstawienia danych wejściowych.

Notacja O jest najczęściej używana przez programistów jako przybliżona miara czasu, przez jaki obliczenia (algorytm) potrwają, aby zakończyć się, wyrażone jako funkcja wielkości zestawu danych wejściowych.

Duże O jest przydatne do porównania, jak dobrze dwa algorytmy będą się skalować wraz ze wzrostem liczby danych wejściowych.

Dokładniej, notacja Big O służy do wyrażenia asymptotycznego zachowania funkcji. Oznacza to, jak zachowuje się funkcja zbliżająca się do nieskończoności.

W wielu przypadkach „O” algorytmu przypada na jeden z następujących przypadków:

• O (1) - Czas do zakończenia jest taki sam, niezależnie od wielkości zestawu danych wejściowych. Przykładem jest dostęp do elementu tablicy według indeksu.
• O (Log N) - Czas do ukończenia zwiększa się mniej więcej zgodnie z log2 (n). Na przykład 1024 elementy zajmują około dwa razy więcej niż 32 elementy, ponieważ Log2 (1024) = 10 i Log2 (32) = 5. Przykładem jest znalezienie elementu w drzewie wyszukiwania binarnego (BST).
• O (N) - Czas do zakończenia, który skaluje się liniowo z rozmiarem zestawu wejściowego. Innymi słowy, jeśli podwoisz liczbę elementów w zestawie wejściowym, algorytm zajmie około dwa razy więcej. Przykładem jest liczenie elementów na połączonej liście.
• O (N Log N) - Czas do ukończenia zwiększa się o liczbę pozycji razy wynik Log2 (N). Przykładem tego jest sortowanie sterty i szybkie sortowanie .
• O (N ^ 2) - Czas do ukończenia jest mniej więcej równy kwadratowi liczby przedmiotów. Przykładem tego jest sortowanie bąbelkowe .
• O (N!) - Czas do ukończenia jest silnią zbioru wejściowego. Przykładem tego jest rozwiązanie problemu brutalnej siły podróżującego sprzedawcy .

Duże O ignoruje czynniki, które nie wpływają w znaczący sposób na krzywą wzrostu funkcji, gdy wielkość wejściowa rośnie w kierunku nieskończoności. Oznacza to, że stałe dodane lub pomnożone przez funkcję są po prostu ignorowane.

Big O to po prostu sposób na wyrażenie siebie w typowy sposób: „Ile czasu / miejsca zajmuje uruchomienie mojego kodu?”.

Często możesz zobaczyć O (n), O (n ² ), O (nlogn) i tak dalej, wszystko to są tylko sposoby na pokazanie; Jak zmienia się algorytm?

O (n) oznacza, że ​​Big O to n, a teraz możesz pomyśleć: „Co to jest n !?” Cóż, „n” to ilość elementów. Obrazowanie, które chcesz wyszukać w tablicy. Musisz spojrzeć na Każdy element i na „Czy jesteś poprawnym elementem / elementem?” w najgorszym przypadku pozycja znajduje się na ostatnim indeksie, co oznacza, że ​​zajęło tyle czasu, ile jest pozycji na liście, więc mówiąc ogólniej, mówimy „o, hej, n jest uczciwie daną ilością wartości!” .

Zatem możesz zrozumieć, co oznacza „n ² ”, ale aby być bardziej szczegółowym, baw się myślą, że masz prosty, najprostszy z algorytmów sortowania; bąbelkowy. Ten algorytm musi przejrzeć całą listę dla każdego elementu.

Moja lista

1. 1
2. 6
3. 3)

Przepływ byłby następujący:

• Porównaj 1 i 6, który jest największy? Ok 6 jest we właściwej pozycji i idzie do przodu!
• Porównaj 6 i 3, och, 3 to mniej! Przenieśmy to, Ok lista się zmieniła, musimy zacząć od samego początku!

To jest O n ^2, ponieważ musisz spojrzeć na wszystkie elementy na liście, które zawierają elementy „n”. Dla każdego elementu ponownie patrzysz na wszystkie elementy, dla porównania jest to również „n”, więc dla każdego elementu wyglądasz „n” razy, co oznacza n * n = n ²

Mam nadzieję, że jest to tak proste, jak chcesz.

Pamiętaj jednak, że Big O to tylko sposób na wyrażenie siebie w czasie i przestrzeni.

Big O opisuje podstawową naturę algorytmu skalowania.

Istnieje wiele informacji, których Big O nie mówi o danym algorytmie. Tnie kości i podaje tylko informacje o skalowalności algorytmu, w szczególności o tym, jak skaluje się wykorzystanie zasobów (czas lub pamięć) algorytmu w odpowiedzi na „wielkość wejściową”.

Rozważ różnicę między silnikiem parowym a rakietą. Nie są to tylko różne odmiany tej samej rzeczy (jak, powiedzmy, silnik Prius vs. silnik Lamborghini), ale są to zasadniczo różne rodzaje układów napędowych, u ich podstaw. Silnik parowy może być szybszy niż rakieta-zabawka, ale żaden silnik tłokowy nie będzie w stanie osiągnąć prędkości orbitalnego pojazdu startowego. Wynika to z faktu, że systemy te mają różne właściwości skalowania w odniesieniu do stosunku wymaganego paliwa („zużycie zasobów”) do osiągnięcia określonej prędkości („wielkość wejściowa”).

Dlaczego to takie ważne? Ponieważ oprogramowanie radzi sobie z problemami, które mogą różnić się wielkością z czynnikami sięgającymi biliona. Zastanów się przez chwilę. Stosunek między prędkością niezbędną do podróży na Księżyc a prędkością chodzenia przez człowieka jest mniejszy niż 10 000: 1, i jest to absolutnie niewielki rozmiar w porównaniu z zakresem wielkości wejściowych, jakie może napotkać oprogramowanie. A ponieważ oprogramowanie może zmierzyć się z astronomicznym zakresem wielkości wejściowych, istnieje potencjał złożoności algorytmu Big O, jego podstawową skalowalnością jest przebijanie wszelkich szczegółów implementacji.

Rozważ kanoniczny przykład sortowania. Sortowanie bąbelkowe to O (n ² ), a sortowanie przez scalenie to O (n log n). Załóżmy, że masz dwie aplikacje do sortowania: aplikację A, która używa sortowania bąbelkowego, i aplikację B, która wykorzystuje sortowanie scalone, i powiedzmy, że dla wielkości wejściowych około 30 elementów aplikacja A jest 1000 razy szybsza niż aplikacja B podczas sortowania. Jeśli nigdy nie musisz sortować więcej niż 30 elementów, oczywiste jest, że powinieneś preferować aplikację A, ponieważ przy tych rozmiarach wejściowych jest ona znacznie szybsza. Jeśli jednak okaże się, że być może trzeba posortować dziesięć milionów elementów, to można się spodziewać, że aplikacja B faktycznie będzie w tym przypadku tysiące razy szybsza niż aplikacja A, całkowicie ze względu na sposób skalowania każdego algorytmu.

Oto zwykły angielski bestiariusz, którego zwykle używam, wyjaśniając popularne odmiany Big-O

We wszystkich przypadkach preferuj algorytmy znajdujące się wyżej na liście niż algorytmy znajdujące się niżej na liście. Jednak koszt przejścia na droższą klasę złożoności różni się znacznie.

O (1):

Bez wzrostu. Niezależnie od tego, jak duży jest problem, możesz go rozwiązać w tym samym czasie. Jest to nieco analogiczne do nadawania, w którym nadawanie na tej samej odległości wymaga takiej samej ilości energii, niezależnie od liczby osób znajdujących się w zasięgu nadawania.

O (log n ):

Ta złożoność jest taka sama jak dla O (1) tyle że jest tylko trochę gorsza. Dla wszystkich praktycznych celów można to uznać za bardzo duże stałe skalowanie. Różnica w pracy między przetwarzaniem 1 tysiąca a 1 miliarda pozycji to tylko czynnik szósty.

O ( n ):

Koszt rozwiązania problemu jest proporcjonalny do wielkości problemu. Jeśli twój problem podwaja się, wówczas koszt rozwiązania podwaja się. Ponieważ większość problemów musi być w jakiś sposób skanowana do komputera, np. Podczas wprowadzania danych, odczytu dysku lub ruchu sieciowego, jest to ogólnie niedrogi czynnik skalowania.

O ( n log n ):

Ta złożoność jest bardzo podobna do O ( n ) . Dla wszystkich praktycznych celów oba są równoważne. Ten poziom złożoności ogólnie nadal byłby uważany za skalowalny. Dostosowując założenia, niektóre algorytmy O ( n log n ) można przekształcić w algorytmy O ( n ) . Na przykład ograniczenie rozmiaru kluczy zmniejsza sortowanie od O ( n log n ) do O ( n ) .

O ( n ² ):

Rośnie jako kwadrat, gdzie n jest długością boku kwadratu. Jest to to samo tempo wzrostu, co „efekt sieci”, w którym każdy w sieci może znać wszystkich innych w sieci. Wzrost jest drogi. Większość skalowalnych rozwiązań nie może wykorzystywać algorytmów o tym poziomie złożoności bez wykonywania znacznej gimnastyki. Zasadniczo dotyczy to wszystkich innych złożoności wielomianowych - O ( n ^k ) -.

O (2 ⁿ ):

Nie skaluje się. Nie masz nadziei na rozwiązanie jakiegoś nieistotnego problemu. Przydatne, aby wiedzieć, czego unikać, i dla ekspertów znaleźć przybliżone algorytmy w O ( n ^k ) .

Wielkie O jest miarą czasu / przestrzeni wykorzystywanej przez algorytm w stosunku do wielkości jego danych wejściowych.

Jeśli algorytmem jest O (n), czas / przestrzeń wzrośnie z tą samą szybkością, co jego wejście.

Jeśli algorytmem jest O (n ² ), wówczas czas / przestrzeń zwiększają się w tempie kwadratu wejściowego.

i tak dalej.

Jakie jest proste angielskie wytłumaczenie Big O? Przy jak najmniejszej definicji formalnej i prostej matematyce.

Prosty angielski objaśnienie potrzeby notacji Big-O:

Kiedy programujemy, staramy się rozwiązać problem. To, co kodujemy, nazywa się algorytmem. Notacja Big O pozwala nam porównać gorszą wydajność naszych algorytmów w znormalizowany sposób. Specyfikacja sprzętu zmienia się w czasie, a ulepszenia sprzętu mogą skrócić czas działania algorytmów. Ale wymiana sprzętu nie oznacza, że ​​nasz algorytm jest lepszy lub ulepszony w czasie, ponieważ nasz algorytm jest nadal taki sam. Aby umożliwić nam porównanie różnych algorytmów, aby ustalić, czy jeden jest lepszy, czy nie, używamy notacji Big O.

Zwykłe angielskie wyjaśnienie tego, co duża notacja O:

Nie wszystkie algorytmy działają w tym samym czasie i mogą się różnić w zależności od liczby elementów na wejściu, które nazwiemy n . Na tej podstawie bierzemy pod uwagę analizę najgorszych przypadków lub górną granicę czasu działania, gdy n staje się coraz większe. Musimy zdawać sobie sprawę z tego, czym jest n , ponieważ wiele zapisów Big O odnosi się do niego.

Bardzo trudno jest zmierzyć szybkość programów, a kiedy próbujemy, odpowiedzi mogą być bardzo złożone i wypełnione wyjątkami i specjalnymi przypadkami. Jest to duży problem, ponieważ wszystkie te wyjątki i przypadki szczególne są rozpraszające i nieprzydatne, gdy chcemy porównać dwa różne programy, aby dowiedzieć się, który jest „najszybszy”.

W wyniku całej tej nieprzydatnej złożoności ludzie próbują opisać szybkość programów przy użyciu możliwie najmniejszych i najmniej złożonych wyrażeń (matematycznych). Te wyrażenia są bardzo przybliżonymi przybliżeniami: chociaż przy odrobinie szczęścia uchwycą „istotę” tego, czy oprogramowanie jest szybkie czy wolne.

Ponieważ są to przybliżenia, używamy w wyrażeniu litery „O” (Big Oh), jako konwencji, aby zasygnalizować czytelnikowi, że dokonujemy rażącego uproszczenia. (I aby upewnić się, że nikt nie pomyliłby, że wyrażenie jest w jakikolwiek sposób dokładne).

Jeśli czytasz „Och” w znaczeniu „w kolejności” lub „w przybliżeniu”, nie pomylisz się. (Myślę, że wybór Big-Oh mógł być próbą humoru).

Jedyne, co te wyrażenia „Big-Oh” starają się zrobić, to opisać, jak bardzo oprogramowanie zwalnia, gdy zwiększamy ilość danych przetwarzanych przez oprogramowanie. Jeśli podwoimy ilość danych, które należy przetworzyć, czy oprogramowanie potrzebuje dwa razy więcej czasu, aby zakończyć pracę? Dziesięć razy dłużej? W praktyce istnieje bardzo ograniczona liczba wyrażeń big-oh, które możesz napotkać i musisz się martwić:

Dobra:

• O(1) Stała : Uruchomienie programu zajmuje tyle samo czasu, bez względu na to, jak duże jest wejście.
• O(log n) Logarytmiczny : Czas działania programu rośnie tylko powoli, nawet przy dużych wzrostach wielkości danych wejściowych.

Źli:

• O(n) Liniowy : czas działania programu wzrasta proporcjonalnie do wielkości wejścia.
• O(n^k) Wielomian : - Czas przetwarzania rośnie coraz szybciej - jako funkcja wielomianu - wraz ze wzrostem wielkości wejściowej.

... i brzydkie:

• O(k^n) Wykładniczy Czas działania programu rośnie bardzo szybko, nawet przy umiarkowanym wzroście wielkości problemu - praktyczne jest przetwarzanie niewielkich zestawów danych za pomocą algorytmów wykładniczych.
• O(n!) Czynnikowy Czas działania programu będzie dłuższy, niż możesz sobie pozwolić na czekanie na nic poza najmniejszymi i najbardziej trywialnymi zestawami danych.

Prosta, prosta odpowiedź może brzmieć:

Duże O reprezentuje najgorszy możliwy czas / przestrzeń dla tego algorytmu. Algorytm nigdy nie zajmie więcej miejsca / czasu powyżej tego limitu. Duże O reprezentuje złożoność czasu / przestrzeni w skrajnym przypadku.

Ok, moje 2 centy.

Big-O, to stopa wzrostu zasobów zużywanych przez program, wrt rozmiar-problemu-wystąpienia

Zasób: może to być całkowity czas pracy procesora, może to być maksymalna ilość pamięci RAM. Domyślnie odnosi się do czasu procesora.

Powiedzmy, że problemem jest „Znajdź sumę”,

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instancja = {5,10,15} ==> problem-instancja-rozmiar = 3, iteracje w pętli = 3

problem-instancja = {5,10,15,20,25} ==> problem-instancja-rozmiar = 5 iteracji w pętli = 5

W przypadku wprowadzania rozmiaru „n” program rośnie z prędkością iteracji „n” w tablicy. Zatem Big-O jest N wyrażone jako O (n)

Powiedzmy, że problemem jest „Find the Combination”,

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instancja = {5,10,15} ==> problem-instancja-rozmiar = 3, suma iteracji = 3 * 3 = 9

problem-instancja = {5,10,15,20,25} ==> problem-instancja-rozmiar = 5, suma iteracji = 5 * 5 = 25

W przypadku wprowadzania rozmiaru „n” program rośnie z prędkością iteracji „n * n” w tablicy. Zatem Big-O oznacza N ² wyrażone jako O (n ² )

Notacja Big O to sposób na opisanie górnej granicy algorytmu pod względem przestrzeni lub czasu działania. N to liczba elementów problemu (tj. Rozmiar tablicy, liczba węzłów w drzewie itp.) Interesuje nas opisanie czasu działania, gdy n robi się duże.

Kiedy mówimy, że jakiś algorytm to O (f (n)), mówimy, że czas działania (lub wymagana przestrzeń) dla tego algorytmu jest zawsze krótszy niż niektóre stałe czasy f (n).

Stwierdzenie, że wyszukiwanie binarne ma czas działania O (logn), oznacza, że ​​istnieje pewna stała c, którą można pomnożyć log (n) przez to zawsze będzie większa niż czas działania wyszukiwania binarnego. W takim przypadku zawsze będziesz mieć stały współczynnik porównań log (n).

Innymi słowy, gdzie g (n) jest czasem działania twojego algorytmu, mówimy, że g (n) = O (f (n)), gdy g (n) <= c * f (n) gdy n> k, gdzie c i k to niektóre stałe.

„ Co to jest proste angielskie wytłumaczenie Wielkiego O? Przy tak małej formalnej definicji, jak to możliwe i prostej matematyce. ”

Takie pięknie proste i krótkie pytanie wydaje się zasługiwać na równie krótką odpowiedź, jaką student może otrzymać podczas korepetycji.

Notacja Big O po prostu mówi, ile czasu * algorytm może działać w ciągu, tylko pod względem ilości danych wejściowych **.

(* w cudownym czasie bez jednostki !)
(** to jest ważne, ponieważ ludzie zawsze będą chcieli więcej , niezależnie od tego, czy żyją dziś, czy jutro)

Co jest takiego cudownego w notacji Big O, jeśli tak właśnie działa?

• Praktycznie rzecz biorąc, analiza Big O jest tak przydatna i ważna, ponieważ Big O kładzie duży nacisk na własną złożoność algorytmu i całkowicie ignoruje wszystko, co jest jedynie stałą proporcjonalności - jak silnik JavaScript, szybkość procesora, połączenie internetowe i wszystkie te rzeczy, które stają się szybko stać się tak śmiesznie nieaktualne jako model T . Big O koncentruje się na wydajności tylko w taki sposób, który ma takie samo znaczenie dla ludzi żyjących obecnie lub w przyszłości.

• Notacja Big O rzuca także bezpośrednie światło na najważniejszą zasadę programowania / inżynierii komputerowej, która inspiruje wszystkich dobrych programistów do dalszego myślenia i marzeń: jedynym sposobem na osiągnięcie wyników poza powolnym marszem technologii jest wynalezienie lepszego algorytm .

Przykład algorytmu (Java):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Opis algorytmu:

• Ten algorytm przeszukuje listę, pozycja po pozycji, szuka klucza,

• Iteracja każdego elementu na liście, jeśli to klucz, to zwróć True,

• Jeśli pętla zakończyła się bez znalezienia klucza, zwróć False.

Notacja Big-O reprezentuje górną granicę złożoności (czas, przestrzeń, ..)

Aby znaleźć The Big-O o złożoności czasu:

• Oblicz, ile czasu (w odniesieniu do wielkości wejściowej) zajmuje najgorszy przypadek:

• Najgorszy przypadek: klucz nie istnieje na liście.

• Czas (najgorszy przypadek) = 4n + 1

• Czas: O (4n + 1) = O (n) | w Big-O stałe są pomijane

• O (n) ~ Liniowy

Istnieje również Big-Omega, które reprezentują złożoność Best-Case:

• Najlepszy przypadek: klucz jest pierwszym przedmiotem.

• Czas (najlepszy przypadek) = 4

• Czas: Ω (4) = O (1) ~ Instant \ Constant

Big O

f (x) = O ( g (x)), gdy x idzie do a (na przykład a = + ∞) oznacza, że ​​istnieje funkcja k taka, że:

1. f (x) = k (x) g (x)

2. k jest ograniczone w pewnym sąsiedztwie a (jeśli a = + ∞, oznacza to, że istnieją liczby N i M takie, że dla każdego x> N, | k (x) | <M).

Innymi słowy, w prostym języku angielskim: f (x) = O ( g (x)), x → a, oznacza, że ​​w sąsiedztwie a, f rozkłada się na iloczyn g i pewnej funkcji ograniczonej.

Mały o

Nawiasem mówiąc, tutaj jest dla porównania definicja małego o.

f (x) = o ( g (x)), gdy x idzie do oznacza, że ​​istnieje funkcja k taka, że:

1. f (x) = k (x) g (x)

2. k (x) idzie do 0, gdy x idzie do a.

Przykłady

• sin x = O (x) gdy x → 0.

• sin x = O (1) gdy x → + ∞,

• x ² + x = O (x) gdy x → 0,

• x ² + x = O (x ² ) gdy x → + ∞,

• ln (x) = o (x) = O (x) gdy x → + ∞.

Uwaga! Notacja ze znakiem równości „=” używa „fałszywej równości”: to prawda, że ​​o (g (x)) = O (g (x)), ale fałsz, że O (g (x)) = o (g (x)). Podobnie można napisać „ln (x) = o (x), gdy x → + ∞”, ale formuła „o (x) = ln (x)” nie ma sensu.

Więcej przykładów

• O (1) = O (n) = O (n ² ) gdy n → + ∞ (ale nie na odwrót, równość jest „fałszywa”),

• O (n) + O (n ² ) = O (n ² ) gdy n → + ∞

• O (O (n ² )) = O (n ² ) gdy n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ) gdy n → + ∞

Oto artykuł w Wikipedii: https://en.wikipedia.org/wiki/Big_O_notation

Notacja Big O to sposób opisania szybkości działania algorytmu przy dowolnej liczbie parametrów wejściowych, które nazwiemy „n”. Jest to przydatne w informatyce, ponieważ różne maszyny działają z różnymi prędkościami, a samo stwierdzenie, że algorytm zajmuje 5 sekund, niewiele mówi, ponieważ podczas gdy możesz pracować z systemem z ośmiordzeniowym procesorem 4,5 GHz, ja mogę działać 15-letni system 800 MHz, który może potrwać dłużej bez względu na algorytm. Zamiast więc określać szybkość działania algorytmu pod względem czasu, mówimy o tym, jak szybko działa pod względem liczby parametrów wejściowych lub „n”. Opisując algorytmy w ten sposób, jesteśmy w stanie porównać prędkości algorytmów bez konieczności uwzględniania prędkości samego komputera.

Nie jestem pewien, czy w dalszym ciągu przyczyniam się do tego tematu, ale nadal myślałem, że mógłbym się podzielić: kiedyś znalazłem ten post na blogu, który zawiera kilka bardzo pomocnych (choć bardzo podstawowych) wyjaśnień i przykładów na temat Big O:

Dzięki przykładom pomogło mi to zdobyć podstawy w mojej czaszce w kształcie skorupy żółwia, więc myślę, że to 10-minutowe czytanie, które prowadzi cię we właściwym kierunku.

Chcesz wiedzieć wszystko, co trzeba wiedzieć o dużym O? Ja też.

Mówiąc o wielkim O, użyję słów, które zawierają tylko jeden bit. Jeden dźwięk na słowo. Małe słowa są szybkie. Znasz te słowa, podobnie jak ja. Użyjemy słów z jednym dźwiękiem. One są małe. Jestem pewien, że poznasz wszystkie słowa, których użyjemy!

A teraz pomówmy o pracy. Przez większość czasu nie lubię pracy. Lubisz pracę Być może tak jest, ale jestem pewien, że nie.

Nie lubię chodzić do pracy. Nie lubię spędzać czasu w pracy. Gdybym miał po swojemu, chciałbym po prostu grać i robić fajne rzeczy. Czy czujesz to samo co ja?

Czasami muszę iść do pracy. To smutne, ale prawdziwe. Więc kiedy jestem w pracy, mam zasadę: staram się wykonywać mniej pracy. Tak blisko pracy, jak tylko mogę. Potem idę grać!

Oto ważna wiadomość: duże O może mi pomóc nie wykonywać pracy! Mogę grać więcej czasu, jeśli znam duży O. Mniej pracy, więcej zabawy! To pomaga mi duże O.

Teraz mam trochę pracy. Mam tę listę: raz, dwa, trzy, cztery, pięć, sześć. Muszę dodać wszystkie rzeczy z tej listy.

Wow, nienawidzę pracy. Ale cóż, muszę to zrobić. Więc proszę.

Jeden plus dwa to trzy ... plus trzy to sześć ... a cztery to ... Nie wiem. Zgubiłem się. To jest dla mnie zbyt trudne do zrobienia. Nie obchodzi mnie tego rodzaju praca.

Więc nie wykonujmy tej pracy. Pomyślmy, jak ciężko jest. Ile pracy musiałbym zrobić, aby dodać sześć liczb?

Więc, zobaczmy. Muszę dodać jeden i dwa, a następnie dodać do trzech, a następnie dodać do czterech… Podsumowując, liczę sześć dodatków. Muszę dodać sześć dodatków, aby rozwiązać ten problem.

Nadchodzi wielki O, aby powiedzieć nam, jak trudna jest ta matematyka.

Wielkie O mówi: musimy rozwiązać sześć problemów. Jeden dodaj, dla każdej rzeczy od jednego do sześciu. Sześć małych kawałków pracy ... każdy kawałek pracy to jeden dodatek.

Cóż, nie zrobię pracy, aby je teraz dodać. Ale wiem, jakie to byłoby trudne. Będzie to sześć dodatków.

O nie, teraz mam więcej pracy. Do licha. Kto robi takie rzeczy ?!

Teraz proszą mnie o dodanie od jednego do dziesięciu! Dlaczego miałbym to zrobić? Nie chciałem dodawać od jednego do sześciu. Aby dodać od jednego do dziesięciu… cóż… byłoby to jeszcze trudniejsze!

O ile trudniej by to było? Ile jeszcze pracy musiałbym wykonać? Czy potrzebuję mniej więcej kroków?

Cóż, chyba musiałbym zrobić dziesięć dodań… po jednym dla każdej rzeczy od jednego do dziesięciu. Dziesięć to więcej niż sześć. Musiałbym pracować o wiele więcej, aby dodać od jednego do dziesięciu, niż od jednego do sześciu!

Nie chcę teraz dodawać. Chcę tylko pomyśleć, jak ciężko może być tak dużo dodawać. Mam nadzieję, że zagram tak szybko, jak tylko będę mógł.

Aby dodać od jednego do sześciu, to trochę pracy. Ale widzisz, aby dodać od jednego do dziesięciu, to więcej pracy?

Big O to twój przyjaciel i mój. Big O pomaga nam zastanowić się, ile pracy musimy wykonać, abyśmy mogli zaplanować. A jeśli jesteśmy przyjaciółmi z wielkim O, może pomóc nam wybrać pracę, która nie jest tak trudna!

Teraz musimy wykonać nową pracę. O nie. W ogóle nie lubię tej pracy.

Nowa praca to: dodaj wszystkie rzeczy od jednego do n.

Czekać! Co to jest n? Czy tęskniłem? Jak mogę dodać od jednego do n, jeśli nie powiesz mi, co to jest n?

Cóż, nie wiem co to jest n. Nie powiedziano mi Byłeś? Nie? No cóż. Więc nie możemy wykonać pracy. Uff

Ale chociaż nie wykonamy teraz pracy, możemy odgadnąć, jak ciężko by to było, gdybyśmy wiedzieli n. Musielibyśmy dodać n rzeczy, prawda? Oczywiście!

Teraz nadchodzi wielki O, a on powie nam, jak ciężka jest ta praca. Mówi: dodawanie wszystkich rzeczy od jednego do N, jeden po drugim, to O (n). Aby dodać te wszystkie rzeczy, [wiem, że muszę dodać n razy.] [1] To jest wielkie O! Mówi nam, jak ciężko jest wykonać jakąś pracę.

Dla mnie myślę o wielkim O jak dużym, powolnym szefie. Myśli o pracy, ale tego nie robi. Mógłby powiedzieć: „Ta praca jest szybka”. Lub może powiedzieć: „Ta praca jest tak powolna i ciężka!” Ale on nie wykonuje pracy. Po prostu patrzy na pracę, a następnie mówi nam, ile czasu może to zająć.

Bardzo mi zależy na wielkim O. Dlaczego? Nie lubię pracować! Nikt nie lubi pracować. Dlatego wszyscy kochamy duże O! Mówi nam, jak szybko możemy pracować. Pomaga nam pomyśleć o ciężkiej pracy.

Och, więcej pracy. Teraz nie wykonujmy pracy. Ale zróbmy krok po kroku plan, aby to zrobić.

Dali nam talię dziesięciu kart. Wszystkie są pomieszane: siedem, cztery, dwa, sześć… wcale nie są proste. A teraz ... naszym zadaniem jest ich uporządkowanie.

Ergh. Brzmi jak dużo pracy!

Jak możemy posortować tę talię? Mam plan.

Będę patrzył na każdą parę kart, para po parze, przez talię, od pierwszego do ostatniego. Jeśli pierwsza karta w jednej parze jest duża, a następna karta w tej parze jest mała, zamieniam je. W przeciwnym razie przechodzę do następnej pary itd. I tak dalej ... i wkrótce pokład jest gotowy.

Po zakończeniu talii pytam: czy zamieniłem karty w tej przepustce? Jeśli tak, muszę zrobić to jeszcze raz, od góry.

W pewnym momencie, w pewnym momencie, nie będzie żadnych zamian, a nasza talia się skończy. Tak dużo pracy!

Cóż, ile by to kosztowało posortowanie kart według tych zasad?

Mam dziesięć kart. I przez większość czasu - to znaczy, jeśli nie mam dużo szczęścia - muszę przejść całą talię do dziesięciu razy, z maksymalnie dziesięcioma kartami wymiany za każdym razem w talii.

Big O, pomóż mi!

Wchodzi duże O i mówi: dla talii n kart, posortowanie go w ten sposób zostanie wykonane w czasie O (N do kwadratu).

Dlaczego on mówi n do kwadratu?

Wiesz, że n do kwadratu to n razy n. Teraz rozumiem: n sprawdzonych kart, aż do tego, co może być n razy w talii. To są dwie pętle, każda z n krokami. To dużo pracy do zrobienia. Na pewno dużo pracy!

Teraz, gdy duże O mówi, że zajmie to O (n-kwadrat) praca, nie ma na myśli n-kwadratowych dodatków na nosie. W niektórych przypadkach może to być trochę mniej. Ale w najgorszym przypadku posortowanie talii będzie blisko n do kwadratu.

Oto, gdzie wielki O jest naszym przyjacielem.

Duże O wskazuje na to: gdy n staje się duże, kiedy sortujemy karty, zadanie staje się DUŻO WIĘKSZE TWARDE, niż stare zadanie po prostu dodaj te rzeczy. Skąd to wiemy?

Cóż, jeśli n stanie się naprawdę duże, nie obchodzi nas, co moglibyśmy dodać do n lub n do kwadratu.

Dla dużych n kwadrat n jest większy niż n.

Big O mówi nam, że sortowanie rzeczy jest trudniejsze niż dodawanie. O (n do kwadratu) jest większe niż O (n) dla dużego n. Oznacza to: jeśli n stanie się naprawdę duże, posortowanie mieszanej talii n MUSI zająć więcej czasu, niż tylko dodanie n mieszanych rzeczy.

Big O nie rozwiązuje dla nas pracy. Big O mówi nam, jak ciężka jest praca.

Mam talię kart. Uporządkowałem je. Pomogłeś. Dzięki.

Czy istnieje szybszy sposób sortowania kart? Czy duży O może nam pomóc?

Tak, jest szybszy sposób! Nauka zajmuje trochę czasu, ale działa ... i działa dość szybko. Możesz też spróbować, ale nie spiesz się z każdym krokiem i nie trać miejsca.

W tym nowym sposobie sortowania talii nie sprawdzamy par kart w sposób, w jaki robiliśmy to przed chwilą. Oto twoje nowe zasady sortowania tej talii:

Po pierwsze: wybieram jedną kartę w części talii, nad którą teraz pracujemy. Możesz wybrać jeden dla mnie, jeśli chcesz. (Gdy robimy to po raz pierwszy, „częścią talii, nad którą teraz pracujemy”, jest oczywiście cała talia).

Po drugie: Odkładam talię na wybraną kartę. Co to za gra; jak mam grać? Cóż, przechodzę od karty startowej w dół, jeden po drugim, i szukam karty, która jest wyższa niż karta do gry.

Po trzecie: przechodzę od karty końcowej do góry i szukam karty, która jest niższa niż karta do gry.

Po znalezieniu tych dwóch kart wymieniam je i szukam kolejnych kart do zamiany. To znaczy, wracam do kroku drugiego i odkładam kartę, którą wybrałeś jeszcze bardziej.

W pewnym momencie ta pętla (od dwóch do trzech) zakończy się. Kończy się, gdy obie połówki tego poszukiwania spotykają się na karcie gry. Następnie właśnie rozłożyliśmy talię kartą wybraną w kroku pierwszym. Teraz wszystkie karty na początku są bardziej niskie niż karta do gry; a karty na końcu są wyższe niż karta do gry. Fajna sztuczka!

Cztery (i to jest zabawne): Mam teraz dwie małe talie, jedną niższą niż karta do gry i jeszcze jedną wyższą. Teraz idę do kroku pierwszego na każdym małym pokładzie! To znaczy, zaczynam od kroku pierwszego na pierwszym małym pokładzie, a kiedy ta praca jest skończona, zaczynam od kroku pierwszego na następnym małym pokładzie.

Rozbijam pokład na części i sortuję każdą część, coraz mniejszą i mniejszą, i w pewnym momencie nie mam już nic do roboty. Teraz może to wydawać się powolne, z wszystkimi zasadami. Ale zaufaj mi, to wcale nie jest wolne. To znacznie mniej pracy niż pierwszy sposób sortowania rzeczy!

Jak się nazywa ten rodzaj? Nazywa się to Szybkim sortowaniem! Tego rodzaju dokonał człowiek o imieniu CAR Hoare który nazwał to Szybkim Sortowaniem. Teraz Szybkie sortowanie jest przyzwyczajone przez cały czas!

Szybkie sortowanie rozbija duże talie na małe. Innymi słowy, dzieli małe zadania na mniejsze.

Hmmm. Myślę, że może tam być reguła. Aby małe zadania były małe, podziel je.

Ten rodzaj jest dość szybki. Jak szybko Duże O mówi nam: ten rodzaj wymaga O (n log n) pracy do wykonania, w średnim przypadku.

Czy jest mniej więcej szybki niż pierwszy? Big O, proszę o pomoc!

Pierwszy rodzaj to O (n-kwadrat). Ale szybkie sortowanie to O (n log n). Wiesz, że n log n jest mniejsze niż n do kwadratu, dla dużego n, prawda? W ten sposób wiemy, że Szybkie sortowanie jest szybkie!

Jeśli musisz posortować talię, jaki jest najlepszy sposób? Możesz robić, co chcesz, ale wybrałbym Szybkie sortowanie.

Dlaczego wybieram Szybkie sortowanie? Oczywiście nie lubię pracować! Chcę, aby praca została wykonana tak szybko, jak to możliwe.

Skąd mam wiedzieć, że Szybkie sortowanie to mniej pracy? Wiem, że O (n log n) jest mniejsze niż O (n kwadratu). O są mniejsze, więc szybkie sortowanie to mniej pracy!

Teraz znasz mojego przyjaciela, Big O. Pomaga nam wykonać mniej pracy. A jeśli znasz duże O, możesz też wykonać mniej pracy!

Nauczyłeś się tego wszystkiego ze mną! Jesteś taki mądry! Dziękuję bardzo!

Teraz, gdy praca jest skończona, chodźmy się pobawić!

[1]: Istnieje sposób na oszukiwanie i dodawanie wszystkich rzeczy od jednego do n, wszystkie naraz. Jakiś dzieciak o imieniu Gauss dowiedział się o tym, gdy miał osiem lat. Nie jestem jednak bystry, więc nie pytaj mnie, jak to zrobił .

Mam prostszy sposób, aby zrozumieć złożoność czasu, którego najbardziej powszechną miarą do obliczania złożoności czasu jest notacja Big O. To usuwa wszystkie stałe czynniki, dzięki czemu czas działania można oszacować w odniesieniu do N, gdy N zbliża się do nieskończoności. Ogólnie możesz myśleć o tym w ten sposób:

statement;

Jest stały. Czas działania instrukcji nie zmieni się w stosunku do N.

for ( i = 0; i < N; i++ )
  statement;

Jest liniowy. Czas działania pętli jest wprost proporcjonalny do N. Gdy N podwaja się, to także czas działania.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

Jest kwadratowy. Czas działania dwóch pętli jest proporcjonalny do kwadratu N. Gdy N podwaja się, czas działania wzrasta o N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

Jest logarytmiczny. Czas działania algorytmu jest proporcjonalny do liczby przypadków, w których N można podzielić przez 2. Dzieje się tak, ponieważ algorytm dzieli obszar roboczy na pół przy każdej iteracji.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Czy N * log (N). Czas działania składa się z N pętli (iteracyjnej lub rekurencyjnej), które są logarytmiczne, dlatego algorytm jest kombinacją liniowej i logarytmicznej.

Ogólnie rzecz biorąc, robienie czegoś z każdym przedmiotem w jednym wymiarze jest liniowe, robienie czegoś z każdym przedmiotem w dwóch wymiarach jest kwadratowe, a dzielenie obszaru roboczego na pół jest logarytmiczne. Istnieją inne miary Big O, takie jak sześcienny, wykładniczy i pierwiastek kwadratowy, ale nie są one tak powszechne. Duża notacja O jest opisana jako O (), gdzie jest miarą. Algorytm szybkiego sortowania zostałby opisany jako O (N * log (N)).

Uwaga: Żadna z tych opcji nie uwzględniała najlepszych, średnich i najgorszych miar. Każdy miałby własną notację Big O. Zauważ też, że jest to BARDZO uproszczone wyjaśnienie. Duże O jest najbardziej powszechne, ale pokazałem też, że jest bardziej złożone. Istnieją również inne zapisy, takie jak duża omega, mała o i duża theta. Prawdopodobnie nie spotkasz ich poza kursem analizy algorytmów.

• Zobacz więcej na: tutaj

Załóżmy, że zamówiłeś Harry'ego Pottera: Kompletna kolekcja 8 filmów [Blu-ray] od Amazon i pobierz tę samą kolekcję filmów online w tym samym czasie. Chcesz przetestować, która metoda jest szybsza. Dostawa trwa prawie dzień, a pobieranie zakończone około 30 minut wcześniej. Świetny! To zacięty wyścig.

Co się stanie, jeśli zamówię kilka filmów Blu-ray, takich jak Władca pierścieni, Zmierzch, Trylogia Mroczny rycerz itp., I jednocześnie pobiorę wszystkie filmy online? Tym razem dostawa nadal trwa jeden dzień, ale pobieranie online trwa 3 dni. W przypadku zakupów online liczba zakupionych produktów (danych wejściowych) nie wpływa na czas dostawy. Wyjście jest stałe. Nazywamy to O (1) .

W przypadku pobierania online czas pobierania jest wprost proporcjonalny do rozmiarów plików filmowych (wejściowych). Nazywamy to O (n) .

Z eksperymentów wiemy, że zakupy online skalują się lepiej niż pobieranie online. Bardzo ważne jest zrozumienie dużej notacji O, ponieważ pomaga ona analizować skalowalność i wydajność algorytmów.

Uwaga: Notacja Big O reprezentuje najgorszy scenariusz algorytmu. Załóżmy, że O (1) i O (n) są najgorszymi scenariuszami z powyższego przykładu.

Odniesienie : http://carlcheo.com/compsci

Załóżmy, że mówimy o algorytmie A , który powinien zrobić coś ze zbiorem danych o rozmiarze n .

Następnie O( <some expression X involving n> )oznacza w prostym języku angielskim:

Jeśli masz pecha podczas wykonywania A, wykonanie operacji X (n) może zająć tyle samo.

Jak to się dzieje, istnieją pewne funkcje (myśleć o nich jako wdrożeń z X (n) ), które zdarzają się dość często. Są to dobrze znane i łatwo stosunku (przykłady: 1, Log N, N, N^2, N!, itp ..)

Porównując je, gdy mówimy o A i innych algorytmów, to jest łatwe do rangi algorytmy według liczby operacji oni mogą (najgorszy przypadek) wymagają, aby zakończyć.

Zasadniczo naszym celem będzie znalezienie lub skonstruowanie algorytmu A w taki sposób, aby miał on funkcję X(n)zwracającą jak najmniejszą liczbę.

Jeśli masz w głowie odpowiednie pojęcie nieskończoności, istnieje bardzo krótki opis:

Notacja Big O informuje o koszcie rozwiązania nieskończenie dużego problemu.

A ponadto

Stałe czynniki są nieistotne

Jeśli przejdziesz na komputer, który może uruchomić algorytm dwa razy szybciej, duża notacja O nie zauważy tego. Ciągłe ulepszenia czynników są zbyt małe, aby można je było zauważyć nawet w skali, z którą współpracuje duża notacja O. Zauważ, że jest to celowa część projektu dużej notacji O.

Chociaż można jednak wykryć coś „większego” niż stały czynnik.

Jeśli jesteś zainteresowany wykonywaniem obliczeń, których rozmiar jest wystarczająco „duży”, aby uznać go za w przybliżeniu nieskończoność, wówczas duża notacja O jest w przybliżeniu kosztem rozwiązania twojego problemu.

Jeśli powyższe nie ma sensu, nie masz w głowie zgodnego intuicyjnego pojęcia nieskończoności i prawdopodobnie powinieneś zignorować wszystkie powyższe; jedynym sposobem, w jaki potrafię uczynić te pomysły rygorystycznymi lub wyjaśnić je, jeśli nie są one intuicyjnie przydatne, jest najpierw nauczyć cię dużej notacji O lub czegoś podobnego. (chociaż, gdy dobrze zrozumiesz dużą notację O w przyszłości, warto ponownie przyjrzeć się tym pomysłom)

Jakie jest proste angielskie wytłumaczenie notacji „Big O”?

Bardzo szybka uwaga:

O w „Big O” odnosi się do „porządku” (a dokładnie „porządku”),
więc możesz dosłownie zrozumieć, że jest używany do zamówienia czegoś, aby je porównać.

• „Big O” robi dwie rzeczy:

  1. Szacuje liczbę kroków metody zastosowanej przez komputer do wykonania zadania.
  2. Ułatwić proces porównywania z innymi, aby ustalić, czy jest dobry, czy nie?
  3. „Big O” osiąga powyższe dwa dzięki standaryzacji Notations.

• Istnieje siedem najczęściej używanych notacji

  1. O (1) oznacza, że ​​komputer wykonuje zadanie krokowo 1, jest doskonały, zamówiony nr 1
  2. O (logN), oznacza, że ​​komputer wykonuje zadanie logNkrokami, jest dobry, zamówiony nr 2
  3. O (N), zakończ zadanie Nkrokami, jego sprawiedliwość, zamówienie nr 3
  4. O (NlogN), kończy zadanie O(NlogN)krokami, nie jest dobrze, zamówienie nr 4
  5. O (N ^ 2), N^2wykonaj zadanie krokami, to źle, zamówienie nr 5
  6. O (2 ^ N), 2^Nwykonaj zadanie krokami, to okropne, rozkaz nr 6
  7. O (N!), Wykonaj zadanie N!krokami, to okropne, rozkaz nr 7

Załóżmy, że otrzymujesz notację O(N^2), nie tylko jesteś pewien, że metoda wymaga N * N kroków, aby wykonać zadanie, ale także widzisz, że nie jest to dobre jak na O(NlogN)podstawie jego rankingu.

Proszę zwrócić uwagę na kolejność na końcu linii, tylko dla lepszego zrozumienia. Istnieje więcej niż 7 notacji, jeśli uwzględniono wszystkie możliwości.

W CS zestaw kroków do wykonania zadania nazywa się algorytmami.
W terminologii notacja Big O jest używana do opisania wydajności lub złożoności algorytmu.

Ponadto Big O określa najgorszy przypadek lub mierzy kroki w górnej części.
W najlepszym przypadku możesz odnieść się do Big-Ω (Big-Omega).

Notacja Big-Ω (Big-Omega) (artykuł) | Khan academy

• Podsumowanie
  „Big O” opisuje wydajność algorytmu i ocenia go.

  lub formalnie go rozwiązać, „Big O” klasyfikuje algorytmy i standaryzuje proces porównywania.

Najprostszy sposób na to spojrzeć (zwykłym angielskim)

Próbujemy zobaczyć, jak liczba parametrów wejściowych wpływa na czas działania algorytmu. Jeśli czas działania aplikacji jest proporcjonalny do liczby parametrów wejściowych, wówczas mówi się, że jest w Wielkim O z n.

Powyższe stwierdzenie to dobry początek, ale nie do końca prawda.

Bardziej dokładne wyjaśnienie (matematyczne)

Przypuszczać

n = liczba parametrów wejściowych

T (n) = Rzeczywista funkcja wyrażająca czas działania algorytmu jako funkcja n

c = stała

f (n) = Przybliżona funkcja wyrażająca czas działania algorytmu jako funkcja n

Jeśli chodzi o Big O, przybliżenie f (n) jest uważane za wystarczająco dobre, o ile spełniony jest poniższy warunek.

lim     T(n) ≤ c×f(n)
n→∞

Równanie odczytuje się, gdy n zbliża się do nieskończoności, T of n jest mniejsze lub równe c razy f od n.

W dużej notacji O jest to zapisane jako

T(n)∈O(n)

Odczytuje się to, gdy T of n jest w dużym O z n.

Powrót do angielskiego

Opierając się na powyższej definicji matematycznej, jeśli powiesz, że twój algorytm jest dużym O z n, oznacza to, że jest funkcją n (liczba parametrów wejściowych) lub szybszą . Jeśli twoim algorytmem jest Big O z n, to automatycznie jest to również Big O z n kwadratu.

Duże O oznacza, że ​​mój algorytm działa co najmniej tak szybko, jak ten. Nie możesz spojrzeć na notację Big O swojego algorytmu i powiedzieć, że jest powolna. Możesz tylko powiedzieć, że jest szybki.

Sprawdzić to się samouczek wideo na Big O z UC Berkeley. To właściwie prosta koncepcja. Jeśli usłyszysz wyjaśnienie profesora Shewchucka (aka nauczyciela na poziomie Boga), powiesz „Och, to wszystko!”.

Znalazłem naprawdę świetne wytłumaczenie dużej notacji O, szczególnie dla kogoś, kto nie interesuje się matematyką.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Notacja O jest używana w informatyce do opisania wydajności lub złożoności algorytmu. Duże O opisuje konkretnie najgorszy scenariusz i może być użyte do opisania wymaganego czasu wykonania lub wykorzystanego miejsca (np. W pamięci lub na dysku) przez algorytm.

Każdy, kto czyta Perły programistyczne lub inne książki z informatyki i nie ma podstaw w matematyce, uderzy o ścianę, gdy dotrze do rozdziałów, które wspominają O (N log N) lub inną pozornie szaloną składnię. Mam nadzieję, że ten artykuł pomoże ci zrozumieć podstawy Big O i Logarytmów.

Jako programista jako pierwszy, a matematyk jako drugi (a może trzeci lub czwarty), znalazłem najlepszy sposób na dokładne zrozumienie Big O, aby stworzyć kilka przykładów w kodzie. Poniżej znajdują się niektóre typowe rzędy wzrostu wraz z opisami i przykładami, jeśli to możliwe.

O (1)

O (1) opisuje algorytm, który zawsze będzie wykonywany w tym samym czasie (lub spacji) bez względu na rozmiar zestawu danych wejściowych.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

NA)

O (N) opisuje algorytm, którego wydajność będzie rosła liniowo i wprost proporcjonalnie do wielkości zbioru danych wejściowych. Poniższy przykład pokazuje również, w jaki sposób Big O faworyzuje scenariusz dotyczący wydajności w najgorszym przypadku; podczas każdej iteracji pętli for można było znaleźć pasujący ciąg, a funkcja powróciłaby wcześniej, ale notacja Big O zawsze zakłada górną granicę, w której algorytm wykona maksymalną liczbę iteracji.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) reprezentuje algorytm, którego wydajność jest wprost proporcjonalna do kwadratu wielkości zbioru danych wejściowych. Jest to typowe w przypadku algorytmów obejmujących zagnieżdżone iteracje w zbiorze danych. Głębsze zagnieżdżone iteracje spowodują O (N ³ ), O (N ⁴ ) itd.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) oznacza algorytm, którego wzrost podwaja się z każdym dodatkiem do zestawu danych wejściowych. Krzywa wzrostu funkcji O (2 ^N ) jest wykładnicza - zaczyna się bardzo płytko, a następnie gwałtownie rośnie. Przykładem funkcji O (2 ^N ) jest rekurencyjne obliczanie liczb Fibonacciego:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logarytmy

Logarytmy są nieco trudniejsze do wyjaśnienia, dlatego skorzystam ze wspólnego przykładu:

Wyszukiwanie binarne to technika używana do wyszukiwania posortowanych zestawów danych. Działa, wybierając środkowy element zestawu danych, zasadniczo medianę, i porównuje go z wartością docelową. Jeśli wartości będą zgodne, zwróci sukces. Jeśli wartość docelowa jest wyższa niż wartość elementu sondy, zajmie ona górną połowę zestawu danych i wykona tę samą operację na nim. Podobnie, jeśli wartość docelowa jest niższa niż wartość elementu sondy, wykona operację względem dolnej połowy. Będzie kontynuował zmniejszanie o połowę zestawu danych przy każdej iteracji, aż do znalezienia wartości lub do momentu, gdy nie będzie już w stanie podzielić zestawu danych.

Ten typ algorytmu jest opisany jako O (log N). Iteracyjne zmniejszenie o połowę zestawów danych opisanych w przykładzie wyszukiwania binarnego tworzy krzywą wzrostu, która osiąga wartość szczytową na początku i powoli spłaszcza się wraz ze wzrostem rozmiaru zestawów danych, np. Zestaw danych wejściowych zawierający 10 elementów zajmuje jedną sekundę, zestaw danych zawierający 100 elementów zajmuje dwie sekundy, a zestaw danych zawierający 1000 elementów zajmuje trzy sekundy. Podwojenie rozmiaru zestawu danych wejściowych ma niewielki wpływ na jego wzrost, ponieważ po jednej iteracji algorytmu zestaw danych zostanie zmniejszony o połowę, a zatem na równi z zestawem danych wejściowych o połowę mniejszym. To sprawia, że ​​algorytmy takie jak wyszukiwanie binarne są wyjątkowo wydajne w przypadku dużych zestawów danych.

To bardzo uproszczone wyjaśnienie, ale mam nadzieję, że obejmuje najważniejsze szczegóły.

Powiedzmy, że twój algorytm radzący sobie z problemem zależy od pewnych „czynników”, na przykład niech N i X.

W zależności od N i X twój algorytm będzie wymagał pewnych operacji, na przykład w przypadku WORST 3(N^2) + log(X) operacje.

Ponieważ Big-O nie przejmuje się zbytnio stałym współczynnikiem (aka 3), Big-O twojego algorytmu to O(N^2 + log(X)). Zasadniczo tłumaczy „ilość operacji potrzebnych algorytmowi w najgorszym przypadku skaluje się z tym”.

Przedmowa

algorytm : procedura / formuła rozwiązania problemu

Jak analizować algorytmy i jak możemy porównywać algorytmy względem siebie?

przykład: ty i przyjaciel jesteście proszeni o utworzenie funkcji sumującej liczby od 0 do N. Wymyślisz f (x), a twój przyjaciel wymyśli g (x). Obie funkcje mają ten sam wynik, ale inny algorytm. Aby obiektywnie porównać efektywność algorytmów, używamy notacji Big-O .

Notacja Big-O: opisuje, jak szybko środowisko uruchomieniowe wzrośnie w stosunku do danych wejściowych, gdy dane wejściowe stają się dowolnie duże.

3 kluczowe dania na wynos:

1. Porównaj, jak szybko rośnie środowisko uruchomieniowe, NIE porównaj dokładnych środowisk uruchomieniowych (zależy od sprzętu)
2. Tylko dotyczy czasu działania rośnie w stosunku do danych wejściowych (n)
3. Ponieważ n staje się dowolnie duże, skup się na warunkach, które będą rosły najszybciej, jak n staje się duże (myśl nieskończoność) analiza asymptotyczna AKA

Złożoność przestrzeni: oprócz złożoności czasu dbamy również o złożoność przestrzeni (ile pamięci / przestrzeni wykorzystuje algorytm). Zamiast sprawdzać czas operacji, sprawdzamy wielkość alokacji pamięci.