Pytanie Co to jest zwykłe angielskie wytłumaczenie zapisu "Big O"?


Wolę jak najmniejszą formalną definicję i prostą matematykę.


4533
2018-01-28 11:10


pochodzenie


Podsumowanie: Górna granica złożoności algorytmu. Zobacz także podobne pytanie Big O, jak to obliczyć / oszacować? dla dobrego wyjaśnienia. - Kosi2801
Pozostałe odpowiedzi są dość dobre, tylko jeden szczegół, aby go zrozumieć: O (log n) lub podobne oznacza, że ​​zależy to od "długości" lub "rozmiaru" danych wejściowych, a nie od samej wartości. To może być trudne do zrozumienia, ale jest bardzo ważne. Na przykład dzieje się tak, gdy twój algorytm dzieli rzeczy na dwie w każdej iteracji. - Harald Schilly
Jest wykład poświęcony złożoności algorytmów w wykładzie 8 kursu MIT "Wprowadzenie do informatyki i programowania" youtube.com/watch?v=ewd7Lf2dr5Q Nie jest to całkowicie zwykły angielski, ale daje ładne wyjaśnienie na przykładach, które są łatwo zrozumiałe. - ivanjovanovic
Big O to oszacowanie najgorszego przypadku wydajności funkcji przy założeniu, że algorytm wykona maksymalną liczbę iteracji. - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


Odpowiedzi:


Krótka uwaga, prawie na pewno jest to mylące Big O notation (która jest górną granicą) z notacją Theta (która jest połączeniem dwustronnym). Z mojego doświadczenia wynika, że ​​jest to typowe dla dyskusji w środowiskach pozaakademickich. Przepraszamy za wszelkie zamieszanie.


O złożoności Big O można wizualizować za pomocą tego wykresu:

Big O Analysis

Najprostszą definicją, jaką mogę podać dla zapisu Big-O jest:

Zapis Big-O jest względną reprezentacją złożoności algorytmu.

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

  • krewny: można tylko porównać jabłka z jabłkami. Nie można porównywać algorytmu do mnożenia arytmetycznego do algorytmu sortującego listę liczb całkowitych. Ale porównanie dwóch algorytmów do wykonywania operacji arytmetycznych (jedno mnożenie, jedno dodanie) powie ci coś znaczącego;
  • reprezentacja: Big-O (w najprostszej postaci) redukuje porównanie algorytmów do pojedynczej zmiennej. Ta zmienna jest wybierana na podstawie obserwacji lub założeń. Na przykład algorytmy sortowania są zazwyczaj porównywane w oparciu o operacje porównania (porównywanie dwóch węzłów w celu ustalenia ich względnej kolejności). Zakłada to, że porównanie jest kosztowne. Ale co, jeśli porównanie jest tanie, ale zamiana jest droga? Zmienia porównanie; i
  • złożoność: jeśli zajmie mi to sekundę, aby posortować 10 000 elementów, ile czasu zajmie mi sortowanie miliona? Złożoność w tym przypadku jest relatywną miarą czegoś innego.

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

Najlepszym przykładem Big-O, jaki mogę sobie wyobrazić, 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 jest nazywana algorytm.

Dodawanie jest najprostsze. Wybierasz numery w górę (w prawo) i dodajesz cyfry w kolumnie, pisząc ostatnią liczbę tego dodatku w wyniku. Część "dziesiątek" tej liczby przenoszona jest 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, musimy dodać 6 cyfr (i ewentualnie mieć 7). Jeśli dodamy dwie 100-cyfrowe liczby, musimy zrobić 100 dodatków. Jeśli dodamy dwa 10 000 cyfr to liczba 10 000 dodatków.

Zobacz wzór? The złożoność (liczba operacji) jest wprost proporcjonalna do liczby cyfr n w większej liczbie. Nazywamy to Na) lub złożoność liniowa.

Odejmowanie jest podobne (z wyjątkiem konieczności pożyczania zamiast przenoszenia).

Mnożenie jest inne. Wybierasz numery w górę, weź pierwszą cyfrę w dolnym numerze i mnoż ją po kolei w stosunku do każdej cyfry w najwyższym numerze i tak dalej za pomocą każdej cyfry. Aby pomnożyć nasze dwie sześciocyfrowe liczby, musimy wykonać 36 multiplikacji. Aby uzyskać końcowy wynik, może być konieczne wykonanie 10 lub 11 kolumn.

Jeśli mamy dwie 100-cyfrowe liczby, musimy wykonać 10 000 multiplikacji i 200 dodatków. W przypadku dwóch milionów cyfr, musimy zrobić jeden trylion (1012) multiplikacje i dwa miliony dodaje.

Ponieważ algorytm skaluje się zdo kwadratu, to jest Na2) lub kwadratowa złożoność. To dobry czas na wprowadzenie kolejnej ważnej koncepcji:

Dbamy tylko o najważniejszą część złożoności.

Wnikliwe może zdać sobie sprawę, że możemy wyrazić liczbę operacji, jak: n2 + 2n. Ale jak widać z naszego przykładu z dwiema liczbami po milion cyfr, drugi termin (2n) staje się nieistotny (odpowiadający 0,0002% wszystkich operacji na tym etapie).

Można zauważyć, że przyjęliśmy tu najgorszy scenariusz. Podczas mnożenia 6 cyfr, jeśli jedna z nich ma 4 cyfry, a druga 6 cyfr, to mamy tylko 24 multiplikacje. Wciąż jednak obliczamy najgorszy scenariusz dla tego "n", tj. Gdy oba są sześciocyfrowe. Stąd zapis Big-O dotyczy scenariusza najgorszego przypadku algorytmu

Książka telefoniczna

Następnym najlepszym przykładem, jaki mogę wymyślić, jest książka telefoniczna, zwykle nazywana White Pages lub podobną, ale będzie się różnić 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.

Teraz, gdybyś polecił komputerowi wyszukać numer telefonu "John Smith" w książce telefonicznej, która zawiera 1 000 000 nazw, co byś zrobił? Ignorując fakt, że możesz się domyślić, jak daleko w S rozpoczęły (załóżmy, że nie możesz), co byś zrobił?

Typową implementacją może być otwarcie się na środek, zdobycie 500 000th i porównaj to z "Smith". Jeśli to się stanie "Smith, John", po prostu mamy szczęście. Znacznie bardziej prawdopodobne jest to, że "John Smith" będzie przed lub po tej nazwie. Jeśli jest po tym, jak dzielimy ostatnią połowę książki telefonicznej na pół i powtarzamy. Jeśli jest to wcześniej, dzielimy pierwszą połowę książki telefonicznej na pół i powtarzamy. I tak dalej.

To się nazywa wyszukiwanie binarne i jest używany codziennie 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 miliony nazwisk, możesz znaleźć dowolną nazwę, wykonując to co najwyżej 20 razy. Porównując algorytmy wyszukiwania, stwierdzamy, że to porównanie jest naszym "n".

  • W przypadku książki telefonicznej zawierającej 3 nazwiska wymaga to 2 porównań (najwyżej).
  • Dla 7 zajmuje to najwyżej 3.
  • Dla 15 to 4.
  • ...
  • Za 1 000 000 potrzeba 20.

To jest oszałamiająco dobre, prawda?

W języku Big-O to jest O (log n) lub złożoność logarytmiczna. Teraz logarytm, o którym mowa, może być ln (base e), log10, log2 lub jakiejś innej bazy. Nie ma znaczenia, że ​​nadal jest O (log n), podobnie jak O (2n2) i O (100n2) nadal są zarówno O (n2).

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

  • Najlepsza sprawa: W wyszukiwaniu książki telefonicznej najlepiej jest znaleźć nazwę w jednym porównaniu. To jest 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 jeden lub drugi z nich będzie ważniejszy.

Powrót do książki telefonicznej.

Co zrobić, jeśli masz numer telefonu i chcesz znaleźć nazwisko? Policja ma odwrotną książkę telefoniczną, ale takie rewizje są odmawiane ogółowi społeczeństwa. Albo czy oni? Technicznie możesz odwrócić wyszukiwanie w zwykłym spisie telefonów. W jaki sposób?

Zaczynasz od imienia i porównujesz numer. Jeśli to pasuje, świetnie, jeśli nie, przejdziesz do następnego. Trzeba to zrobić w ten sposób, ponieważ książka telefoniczna jest niezamówiony (według numeru telefonu).

Aby znaleźć nazwisko z podanym numerem telefonu (wyszukiwanie wsteczne):

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

Podróżujący sprzedawca

Jest to dość znany problem informatyki i zasługuje na wzmiankę. W tym problemie masz N miast. Każde z tych miast jest połączone z jednym lub kilkoma innymi miastami drogą o określonej długości. Problem Traveling Salesman polega na znalezieniu najkrótszej wycieczki, 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 iść:

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

Właściwie 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ż używają tych samych dróg, tylko w odwrotnej kolejności).

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

  • Weź to do 4 miast i masz (iirc) 12 możliwości.
  • Przy 5 jest 60.
  • 6 staje się 360.

Jest to funkcja operacji matematycznej zwanej a Factorial. 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,31,210,043,330,985,984 000 000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3,04140932 × 1064

Tak więc problemem jest Big-O z Traveling Salesman Na!) lub złożoność czynnikowa lub kombinatoryczna.

Kiedy dotrzesz do 200 miast, nie ma wystarczająco dużo czasu, aby rozwiązać problem z tradycyjnymi komputerami.

Coś do przemyślenia.

Wielomianowy czas

Kolejnym punktem, o którym chciałem szybko wspomnieć jest to, że każdy algorytm ma złożoność Naza) podobno ma złożoność wielomianowa lub można go rozwiązać w czas wielomianowy.

O (n), O (n2) itp. są wszystkie wielomian czasu. Niektóre problemy nie mogą zostać rozwiązane w czasie wielomianowym. Z tego powodu pewne rzeczy są używane w świecie. Kryptografia klucza publicznego jest doskonałym przykładem. Obliczeniowo trudno jest znaleźć dwa czynniki pierwsze o bardzo dużej liczbie. Gdyby tak nie było, nie moglibyśmy użyć 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 (poprawione).


6094
2018-01-28 11:18



Podczas gdy inne odpowiedzi koncentrują się na wyjaśnieniu różnic między O (1), O (n ^ 2) i in. .... twoja jest tym, który szczegółowo opisuje, jak algorytmy mogą zostać sklasyfikowane na n ^ 2, nlog (n) itd. 1 na dobrą odpowiedź, która pomogła mi również zrozumieć zapis Big O - Yew Long
można by dodać, że big-O reprezentuje górną granicę (określoną przez algorytm), big-Omega daje niższą granicę (zwykle podaną jako dowód niezależny od określonego algorytmu), a big-Theta oznacza, że ​​"optymalny" algorytm docieranie do tej dolnej granicy jest znane. - mdm
Jest to dobre, jeśli szukasz najdłuższej odpowiedzi, ale nie odpowiedzi, która najlepiej wyjaśnia Big-O w prosty sposób. - kirk.burleson
-1: Jest to rażąco błędne: _ "BigOh jest względną reprezentacją złożoności algorytmu". BigOh jest asymptotyczną górną granicą i istnieje całkiem dobrze niezależnie od informatyki. O (n) jest liniowy. Nie, mylisz BigOh z theta. log n to O (n). 1 oznacza O (n). Liczba upvotes do tej odpowiedzi (i komentarzy), która sprawia, że ​​podstawowy błąd mylenia Theta z BigOh jest dość zawstydzająca ...
"Do czasu, gdy dotrzesz do 200 miast, nie ma wystarczająco dużo czasu we wszechświecie, aby rozwiązać problem z tradycyjnymi komputerami". Kiedy wszechświat się skończy? - Isaac


Pokazuje, jak algorytm się skaluje.

Na2): znany jako Kwadratowa złożoność

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

Zauważ, że liczba przedmiotów zwiększa się o współczynnik 10, ale czas wzrasta dziesięciokrotnie2. Zasadniczo n = 10 i tak O (n2) daje nam współczynnik skalujący n2 która wynosi 102.

Na): znany jako Liniowa złożoność

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

Tym razem liczba przedmiotów zwiększa się o współczynnik 10, podobnie jak czas. n = 10, a więc współczynnik skalowania O (n) wynosi 10.

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

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

Liczba elementów wciąż rośnie o współczynnik 10, ale współczynnik skalowania O (1) ma zawsze wartość 1.

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

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

Liczba obliczeń jest tylko zwiększona przez dziennik wartości wejściowej. Tak więc w tym przypadku, zakładając, że każde obliczenie zajmuje 1 sekundę, log wejścia n jest to czas potrzebny, stąd log n.

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


662
2018-01-28 11:28



co dokładnie oznacza ta definicja? (Liczba elementów wciąż rośnie o współczynnik 10, ale współczynnik skalowania O (1) zawsze wynosi 1.) - HollerTrain
Nie sekundy, operacje. Poza tym traciłeś czas na silniki i logarytmy. - Chris Charabaruk
Nie wyjaśnia to zbyt dobrze, że O (n ^ 2) może opisywać algorytm, który działa dokładnie .01 * n ^ 2 + 999999 * n + 999999. Ważne jest, aby wiedzieć, że algorytmy są porównywane za pomocą tej skali, a to porównanie działa, gdy n jest "wystarczająco duże". Python's timsort faktycznie używa sortowania wstawiania (najgorszy / przeciętny przypadek O (n ^ 2)) dla małych tablic ze względu na fakt, że ma mały narzut. - Darthfett
Ta odpowiedź również dezorientuje dużą notację O i notację Theta. Funkcja n, która zwraca 1 dla wszystkich swoich danych wejściowych (zwykle po prostu zapisanych jako 1), faktycznie znajduje się w O (n ^ 2) (nawet jeśli jest również w O (1)). Podobnie algorytm, który wykonuje tylko jeden krok, który zajmuje stały czas, jest również uważany za algorytm O (1), ale także za algorytm O (n) i O (n ^ 2). Ale może matematycy i informatycy nie zgadzają się co do definicji: - /. - Jacob Akkerboom
O (log n) złożoność logarytmiczna rozpatrywana w tej odpowiedzi jest podstawowa. 10. Ogólnie standardem jest obliczanie za pomocą podstawy 2. Należy pamiętać o tym fakcie i nie należy się mylić. Również jak wspomniano przez @ChrisCharabaruk, złożoność oznacza liczbę operacji, a nie sekundy. - Aksh1801


Notacja Big-O (zwana również notacją asymptotyczną) jakie funkcje "wyglądają", gdy ignorujesz stałe czynniki i rzeczy w pobliżu miejsca pochodzenia. Używamy go, aby mówić jak rzeczy skalują.


Podstawy

dla "wystarczająco" dużych wejść ...

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

notacja big-o nie dba o stałe czynniki: funkcję 9x² mówi się, że "rośnie dokładnie jak" 10x². Ani big-O asymptotyczny dbałość o zapis niesymptotyczny rzeczy ("rzeczy blisko pochodzenia" lub "co się dzieje, gdy rozmiar problemu jest mały"): funkcja 10x² mówi się, że "rośnie dokładnie jak" 10x² - x + 2.

Dlaczego chcesz zignorować mniejsze części równania? Ponieważ stają się całkowicie karłowate przez duże części równania, gdy weźmiesz pod uwagę większe i większe łuski; ich wkład staje się karłowaty i nieistotny. (Patrz przykładowa sekcja.)

Innymi słowy, chodzi tylko o stosunek jak idziesz do nieskończoności. Jeśli podzielisz rzeczywisty czas potrzebny na O(...), dostaniesz stały czynnik w granicach dużych wejść. Intuicyjnie ma to sens: funkcje "skalują się" wzajemnie, jeśli możesz pomnożyć jeden, aby uzyskać drugi. To znaczy, kiedy mówimy ...

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

... to znaczy że dla "wystarczająco dużych" rozmiarów problemu N (jeśli ignorujemy rzeczy zbliżone do początku), istnieje pewna stała (na przykład 2,5, całkowicie zmontowana) taka, że:

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

Istnieje wiele opcji stałych; często "najlepszy" wybór jest znany jako "stały czynnik" algorytmu ... ale często go ignorujemy, tak jak ignorujemy inne niż największe terminy (patrz sekcja "Stałe czynniki", dlaczego zwykle nie mają one znaczenia). Możesz również myśleć o powyższym równaniu jako o związanym, mówiąc "W najgorszym przypadku czas, jaki zajmie, nigdy nie będzie gorszy niż z grubsza N*log(N), przy współczynniku 2,5 (stały czynnik, który nas nie interesuje)".

Ogólnie, O(...) jest najbardziej przydatny, ponieważ często zależy nam na najgorszym przypadku. Gdyby f(x) reprezentuje coś "złego", takiego jak użycie procesora lub pamięci, a następnie "f(x) ∈ O(upperbound)" znaczy "upperbound jest najgorszym scenariuszem użycia procesora / pamięci ".


Aplikacje

Jako czysto matematyczna konstrukcja, notacja big-o nie ogranicza się do mówienia o czasie przetwarzania i pamięci. Możesz go użyć do omawiania asymptotyki wszystkiego, co ma znaczenie, np .:

  • liczba możliwych uścisków dłoni wśród N ludzie na imprezie (Ɵ(N²), konkretnie N(N-1)/2, ale najważniejsze jest to, że "skaluje się" )
  • probabilistyczną spodziewaną liczbę ludzi, którzy widzieli jakiś marketing wirusowy jako funkcję czasu
  • jak skraca się czas oczekiwania na witrynę z liczbą procesorów w procesorze lub GPU lub klastrze komputerowym
  • jak przebiega moc wyjściowa ciepła na CPU, w zależności od liczby tranzystorów, napięcia itp.
  • ile czasu potrzebuje algorytm, w zależności od wielkości wejściowej
  • ile miejsca potrzebuje algorytm, w zależności od wielkości wejściowej

Przykład

Dla powyższego przykładu uścisku dłoni każdy w pokoju potrząsa cudzą ręką. W tym przykładzie #handshakes ∈ Ɵ(N²). Czemu?

Utwórz kopię zapasową: liczba uścisków dłoni to dokładnie n-wybierz-2 lub N*(N-1)/2 (każdy z N ludzi potrząsa rękami N-1 innych ludzi, ale ten podwójny liczy uściski dłoni tak dzielą się przez 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Jednak dla bardzo dużej liczby osób termin liniowy N jest karłowate i efektywnie przyczynia się 0 do stosunku (na wykresie: ułamek pustych pól na przekątnej na sumarycznych polach zmniejsza się wraz ze wzrostem liczby uczestników). Dlatego zachowanie skalowania jest order N²lub liczba uścisków dłoni "rośnie jak N²".

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

Wygląda to tak, jakby puste pola na przekątnej wykresu (znaczniki N * (N-1) / 2) jeszcze tam nie było (N2 zaznaczenia asymptotycznie).

(tymczasowa dygresja od "zwykłego angielskiego" :) Jeśli chciałeś to udowodnić samemu, możesz wykonać prostą algebrę, aby podzielić ją na kilka terminów (limoznacza "rozważany w limicie", po prostu zignoruj ​​go, jeśli go nie widziałeś, to jest po prostu zapis "i N jest naprawdę naprawdę 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" x² tak bardzo dla dużych wartości, że gdybyśmy zapisali stosunek # uściski dłoni / x², fakt, że nie potrzebujemy dokładnie Uściski dłoni x² nie pojawiałyby się nawet w dziesiętnym przez arbitralnie duży czas.

na przykład dla x = 1 mln, stosunek # uściski dłoni / x²: 0,499999 ...


Intuicja budynku

Dzięki temu możemy wydawać oświadczenia, takie jak ...

"Dla wystarczająco dużego inputize = N, bez względu na stały współczynnik, jeśli I podwójnie rozmiar wejściowy


362
2017-07-08 04:46



Doskonała odpowiedź matematyczna, ale OP poprosił o prostą odpowiedź w języku angielskim. Ten poziom opisu matematycznego nie jest konieczny, aby zrozumieć odpowiedź, choć dla osób szczególnie matematycznie myślących może być o wiele prostszy do zrozumienia niż "zwykły angielski". Jednak PO zwrócił się o to drugie. - El Zorko
Prawdopodobnie ludzie inni niż OP mogą być zainteresowani odpowiedziami na to pytanie. Czy to nie jest przewodnia zasada witryny? - Casey
Chociaż może widzę, dlaczego ludzie mogą przejrzeć moją odpowiedź i sądzę, że to zbyt math (zwłaszcza "matematyka to nowy zwykły angielski", odsyła komentarz, ponieważ usunięto), pierwotne pytanie pyta o big-O, który dotyczy funkcji, więc staraj się być wyraźnym i mówić o funkcjach w sposób, który uzupełnia intuicję prostego angielskiego. Tutaj matematyka może być często pomijana lub rozumiana na matematycznym tle liceum. Wydaje mi się, że ludzie mogą na koniec przyjrzeć się dodatkom do matematyki i zakładać, że jest to część odpowiedzi, kiedy wystarczy zobaczyć, real matematyka wygląda. - ninjagecko
To jest fantastyczna odpowiedź; znacznie lepszy IMO niż ten, który ma najwięcej głosów. Wymagana "matematyka" nie wykracza poza to, co jest potrzebne do zrozumienia wyrażeń w nawiasach po "O", czego nie da się uniknąć żadnym rozsądnym wyjaśnieniem, które wykorzystuje jakiekolwiek przykłady. - Dave Abrahams
"f (x) ∈ O (górna granica) oznacza, że ​​f" rośnie nie szybciej niż "górna granica", te trzy proste słowa, ale matematycznie poprawne wyjaśnienia wielkich Oh, Theta i Omega są złote. Opisał mi po angielsku, że pięć różnych źródeł nie może mi się tłumaczyć bez pisania złożonych wyrażeń matematycznych. Dzięki! :) - timbram


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

W jednym zdaniu: Kiedy rozmiar Twojej pracy rośnie, ile jeszcze czasu zajmuje jej ukończenie?

Oczywiście jest to tylko użycie "rozmiaru" jako danych wejściowych, a "czas wykonania" jako danych wyjściowych - ten sam pomysł ma zastosowanie, jeśli chcesz rozmawiać o użyciu pamięci itp.

Oto przykład, gdzie mamy koszulki N, które chcemy wysuszyć. Dobrze założyć jest niesamowicie szybki, aby uzyskać je w pozycji do suszenia (to znaczy interakcja człowieka jest znikoma). Oczywiście tak nie jest w prawdziwym życiu ...

  • Korzystanie z linii mycia na zewnątrz: zakładając, że masz nieskończenie duże podwórko, mycie wysycha w czasie O (1). Jakkolwiek wiele z tego masz, dostanie 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 potem godzinę później. (Zignoruj ​​aktualne liczby - nie mają one znaczenia). Tak więc suszenie trwa 50 koszulek o 5 razy dłużej niż suszenie 10 koszul.

  • Wrzucenie wszystkiego do szafy wietrzeniowej: Jeśli postawimy wszystko na jeden wielki stos i po prostu zrobimy to ciepło, zabierze to na długi czas, aby środkowe koszulki wyschły. Nie chciałbym zgadywać szczegółów, ale podejrzewam, że jest to co najmniej O (N ^ 2) - w miarę zwiększania obciążenia praniem czas suszenia rośnie szybciej.

Ważnym aspektem zapisu "big O" jest to, że jest nie robi powiedz, który algorytm będzie szybszy dla danego rozmiaru. Weź hashtable (klucz łańcucha, wartość całkowita) vs tablicę par (ciąg, liczba całkowita). Czy szybciej jest znaleźć klucz w haśle lub elemencie w tablicy, na podstawie ciągu znaków? (dla tablicy "znajdź pierwszy element, w którym część łańcuchowa pasuje do podanego klucza.") Hashtables są ogólnie amortyzowane (~ = "średnio") O (1) - po ich skonfigurowaniu powinno to zająć około w tym samym czasie, aby znaleźć wpis w tabeli 100 wpisów, tak jak w tabeli 1.000.000 wpisów. Znalezienie elementu w tablicy (na podstawie treści, a nie indeksu) jest liniowe, tj. O (N) - średnio będziesz musiał spojrzeć na połowę wpisów.

Czy powoduje to, że hashtable jest szybsze niż tablica dla wyszukiwań? Niekoniecznie. Jeśli masz bardzo małą kolekcję wpisów, tablica może być szybsza - możesz sprawdzić wszystkie łańcuchy w czasie, który wystarczy, aby obliczyć kod skrótu tego, na który patrzysz. W miarę jak zbiór danych powiększa się, to jednak hashtable ostatecznie pokona tablicę.


237
2018-01-28 11:16



Funkcja hashtable wymaga uruchomienia algorytmu w celu obliczenia indeksu rzeczywistej macierzy (w zależności od implementacji). A tablica ma tylko O ​​(1), ponieważ jest to tylko adres. Ale to nie ma nic wspólnego z pytaniem, tylko obserwacją :) - Filip Ekberg
Wyjaśnienie Jona bardzo pasuje do tego, o czym myślę. to jest dokładnie to, jak można to wytłumaczyć jakiejś mamie, a ona w końcu to zrozumie, myślę :) podoba mi się przykład ubrań (w szczególności ostatni, gdzie wyjaśnia wykładniczy wzrost złożoności) - Johannes Schaub - litb
Filip: Nie mówię o adresowaniu tablicy według indeksu, mówię o znalezieniu pasującego wpisu w tablicy. Czy możesz ponownie przeczytać odpowiedź i zobaczyć, czy to wciąż jest niejasne? - Jon Skeet
@Filip Ekberg Myślę, że myślisz o tabeli adresów bezpośrednich, gdzie każdy indeks mapuje do klucza bezpośrednio stąd jest O (1), jednak wierzę, że Jon mówi o nieposortowanej tablicy par klucz / wal, które musisz przeszukać przez liniowy. - ljs
@RBT: Nie, to nie jest binarne spojrzenie. Może dostać się do właściwego skrótu wiadro natychmiast, w oparciu o transformację z kodu skrótu do indeksu segmentów. Po tym znalezieniu odpowiedniego kodu skrótu w wiadrze może być liniowy lub może być wyszukiwanie binarne ... ale do tego czasu jesteś w dół do bardzo niewielkiej części całkowitej wielkości słownika. - Jon Skeet


Big O opisuje górną granicę wzrostu funkcji, na przykład czas działania programu, gdy dane wejściowe stają się duże.

Przykłady:

  • O (n): Jeśli podwoję rozmiar wejściowy, środowisko uruchomieniowe podwaja się

  • Na2): Jeśli rozmiar wejściowy podwaja czas wykonania czterokrotnie

  • O (log n): Jeśli rozmiar wejściowy podwaja się, środowisko wykonawcze zwiększa się o jeden

  • O (2n): Jeśli rozmiar wejściowy zwiększy się o jeden, środowisko uruchomieniowe podwoi się

Wielkość wejściowa to zwykle spacja w bitach potrzebna do przedstawienia wejścia.


120
2018-01-28 11:23



błędny! na przykład O (n): Jeśli podwoję wielkość wejściową, środowisko wykonawcze będzie mnożyć się do stałej skończonej niezerowej. Mam na myśli O (n) = O (n + n) - arena-ru
Mówię o f in f (n) = O (g (n)), a nie g, jak się wydaje rozumiesz. - starblue
Przegłosowałem, ale ostatnie zdanie nie robi wiele, co czuję. Nie często mówimy o "bitach" podczas omawiania lub mierzenia Big (O). - cdiggins
Powinieneś dodać przykład dla O (n log n). - Christoffer Hammarström
To nie jest takie oczywiste, zasadniczo zachowuje się nieco gorzej niż O (n). Więc jeśli n podwoi, środowisko wykonawcze zostanie pomnożone przez współczynnik nieco większy niż 2. - starblue


Notacja Big O jest najczęściej używana przez programistów jako przybliżona miara czasu trwania obliczeń (algorytmów) wyrażona w zależności od wielkości zestawu wejściowego.

Big O jest przydatny przy porównywaniu, jak dobrze dwa algorytmy skalują się wraz ze wzrostem liczby wejść.

Dokładniej Big O notation służy do wyrażania asymptotycznego zachowania funkcji. Oznacza to, że funkcja zachowuje się w miarę zbliżania się do nieskończoności.

W wielu przypadkach "O" algorytmu można przypisać do jednego z następujących przypadków:

  • O (1) - Czas do zakończenia jest taki sam, niezależnie od wielkości zestawu wejściowego. Przykładem jest uzyskanie dostępu do elementu tablicy według indeksu.
  • O (Log N) - Czas do ukończenia rośnie w przybliżeniu zgodnie z log2 (n). Na przykład 1024 elementów zajmuje około dwa razy dłużej niż 32 elementy, ponieważ Log2 (1024) = 10 i Log2 (32) = 5. Przykładem jest znalezienie elementu w drzewo wyszukiwania binarnego (BST).
  • NA) - Czas na ukończenie skaluje się liniowo z rozmiarem zestawu wejściowego. Innymi słowy, jeśli podwoisz liczbę elementów w zestawie wejściowym, algorytm zajmuje około dwa razy dłużej. Przykładem jest liczba przedmiotów na połączonej liście.
  • O (N Log N) - Czas do zakończenia wzrasta o liczbę elementów w wyniku Log2 (N). Przykładem tego jest sortowanie sterty i szybkie sortowanie.
  • O (N ^ 2) - Czas wykonania jest mniej więcej równy kwadratowi liczby przedmiotów. Przykładem tego jest sortowanie bąbelkowe.
  • NA!) - Czas do zakończenia to silnia zestawu wejściowego. Przykładem tego jest kłopotliwy sprzedawca problem z brute-force.

Big O ignoruje czynniki, które nie przyczyniają się w znaczący sposób do krzywej wzrostu funkcji, gdy wielkość wejściowa wzrasta w kierunku nieskończoności. Oznacza to, że stałe, które są dodawane lub mnożone przez funkcję, są po prostu ignorowane.


97
2017-09-05 16:31



cdiggins, co jeśli mam złożoność O (N / 2), czy powinien to być O (N) lub O (N / 2), na przykład, co to jest złożoność, jeśli zrobię pętlę ponad pół łańcucha. - Melad Ezzat
@Melad Jest to przykład stałej (0,5) pomnożonej przez funkcję. Jest to ignorowane, ponieważ uważa się, że ma znaczący wpływ na bardzo duże wartości N. - cdiggins


Big O to po prostu sposób na "Ekspresję" siebie w zwykły sposób, "Ile czasu / miejsca zajmuje uruchomienie mojego kodu?".

Często można zobaczyć O (n), O (n2), O (nlogn) i tak dalej, wszystkie one są po prostu sposobami pokazania; Jak zmienia się algorytm?

O (n) oznacza, że ​​Big O jest n, a teraz możesz pomyśleć: "Co to jest n !?" Cóż "n" to ilość elementów. Obrazowanie, które chcesz wyszukać element w tablicy. Będziesz musiał spojrzeć na Każdy element i jako "Czy jesteś właściwym elementem / przedmiotem?" w najgorszym przypadku pozycja jest na ostatnim indeksie, co oznacza, że ​​zajęło to tyle samo czasu, ile pozycji na liście, więc aby być ogólną, mówimy "o, hej, n to sprawiedliwa podana wartość!" .

Więc możesz zrozumieć, co "n2"oznacza, ale aby być jeszcze bardziej specyficznym, zagraj z myślą, że masz prosty, najprostszy z algorytmów sortowania, bubblesort. Ten algorytm musi przejrzeć całą listę dla każdego przedmiotu.

Moja lista

  1. 1
  2. 6
  3. 3

Przepływ tutaj będzie:

  • Porównaj 1 i 6, która jest największa? OK 6 jest we właściwej pozycji, posuwa się naprzód!
  • Porównaj 6 i 3, o, 3 to mniej! Przenieśmy to, Ok, lista się zmieniła, musimy zacząć od początku!

To jest O n2 ponieważ musisz przejrzeć wszystkie pozycje na liście, są tam pozycje "n". Dla każdej pozycji ponownie spojrzysz na wszystkie elementy, dla porównania, jest to również "n", więc dla każdej pozycji wyglądasz "n" razy oznaczając n * n = n2

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

Ale pamiętajcie, Big O to tylko sposób na wyodrębnienie się w sposób czasu i przestrzeni.


77
2018-01-28 11:14



dla logN rozważamy dla pętli działającej od 0 do N / 2, co z O (log log N)? Mam na myśli, jak wygląda program? przepraszam za czyste umiejętności matematyczne - Pablo Escobar


Big O opisuje podstawową charakterystykę skalowania algorytmu.

Jest wiele informacji, że Big O nie mówi ci o danym algorytmie. Tnie do kości i podaje tylko informacje o skalowalności algorytmu, w szczególności w jaki sposób wykorzystanie zasobów (czas myślenia lub pamięć) algorytmu skaluje się 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, w ich rdzeniu. Silnik parowy może być szybszy niż rakieta zabawki, ale żaden silnik parowy nie będzie w stanie osiągnąć prędkości orbitalnego pojazdu startowego. Wynika to z tego, że systemy te mają różne charakterystyki skalowania w odniesieniu do stosunku wymaganego paliwa ("wykorzystanie zasobów") do osiągnięcia danej prędkości ("wielkość wejściowa").

Dlaczego to jest takie ważne? Ponieważ oprogramowanie radzi sobie z problemami, które różnią się rozmiarem od czynników do biliona. Pomyśl o tym przez chwilę. Stosunek prędkości niezbędnej do podróży do Księżyca i prędkości chodu człowieka jest mniejszy niż 10 000: 1, a to jest absolutnie małe w porównaniu do zakresu w wejściowych rozmiarach oprogramowania może napotkać. A ponieważ oprogramowanie może napotkać zakres astronomiczny w wejściowych rozmiarach, istnieje potencjał złożoności Big O algorytmu, to jest fundamentalna natura skalowania, aby wyłapać jakiekolwiek szczegóły implementacji.

Rozważ kanoniczny przykład sortowania. Bubble-sort to O (n2) podczas gdy scalanie-sort to O (n log n). Załóżmy, że masz dwie aplikacje do sortowania, aplikację A, która używa sortowania bąbelkowego i aplikacji B, która używa sortowania scalonego, 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 będziesz musiał sortować więcej niż 30 elementów, oczywistym jest, że powinieneś preferować aplikację A, ponieważ jest znacznie szybszy przy tych rozmiarach wejściowych. Jeśli jednak okaże się, że trzeba posortować dziesięć milionów elementów, to można się spodziewać, że aplikacja B faktycznie będzie tysiąc razy szybsza niż aplikacja A w tym przypadku, całkowicie ze względu na sposób skalowania każdego algorytmu.


52
2018-01-28 13:12





Oto zwykły angielski bestiariusz, którego używam przy tłumaczeniu popularnych odmian Big-O

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

O (1):

Bez wzrostu. Bez względu na to, jak duży jest problem, możesz go rozwiązać w tym samym czasie. Jest to w pewnym sensie analogiczne do nadawania, gdy transmisja zajmuje taką samą ilość energii na danej odległości, niezależnie od liczby osób znajdujących się w zasięgu transmisji.

O (log n):

Ta złożoność jest taka sama jak O (1) z tym że jest tylko trochę gorzej. Ze względów praktycznych można to uznać za bardzo duże stałe skalowanie. Różnica w pracy pomiędzy przetwarzaniem 1 i 1 miliarda przedmiotów jest tylko sześciokrotnością.

O (n):

Koszt rozwiązania problemu jest proporcjonalny do rozmiaru problemu. Jeśli Twój problem podwoi się, to koszt rozwiązania podwaja się. Ponieważ większość problemów musi zostać zeskanowana do komputera w jakiś sposób, jako wprowadzanie danych, odczyty dysku lub ruch sieciowy, jest to zwykle niedrogi czynnik skalujący.

O (n log n):

Ta złożoność jest bardzo podobna do O (n). Ze względów praktycznych oba są równoważne. Ten poziom złożoności byłby ogólnie uznany za skalowalny. Ulepszając niektóre założenia O (n log n) Algorytmy mogą zostać przekształcone w O (n) algorytmy. Na przykład ograniczenie rozmiaru klawiszy zmniejsza sortowanie z O (n log n) do O (n).

O (n2):

Rośnie jako kwadrat, gdzie n jest długością boku kwadratu. Jest to ta sama stopa wzrostu co "efekt sieci", w którym wszyscy w sieci mogą znać wszystkich pozostałych w sieci. Wzrost jest drogi. Większość skalowalnych rozwiązań nie może korzystać z algorytmów o takim poziomie złożoności, bez wykonywania znaczących ćwiczeń gimnastycznych. Zasadniczo dotyczy to wszystkich innych złożoności wielomianowych - O (nk) - także.

O (2n):

Nie skaluje. Nie masz nadziei na rozwiązanie żadnego problemu o nielimitowanym rozmiarze. Przydatne, aby wiedzieć, czego unikać, a dla ekspertów znaleźć przybliżone algorytmy, które są w O (nk).


35
2018-01-27 23:09



Czy mógłbyś rozważyć inną analogię dla O (1)? Inżynier we mnie chce wyciągnąć dyskusję na temat impedancji RF z powodu przeszkód. - johnwbyrd
Z jakiegoś powodu użyłem słowa "nieco". - Andrew Prock


Big O jest miarą tego, ile czasu / przestrzeni wykorzystuje algorytm w stosunku do wielkości jego wejścia.

Jeśli algorytm ma wartość O (n), wówczas czas / przestrzeń będzie wzrastać z tą samą szybkością, co wejście.

Jeśli algorytm to O (n2) następnie podniesienie czasu / przestrzeni z szybkością jego wejścia do kwadratu.

i tak dalej.


34
2018-01-28 11:19



Tu nie chodzi o przestrzeń. Chodzi o złożoność, która oznacza czas. - S.Lott
Zawsze uważałem, że może to dotyczyć czasu LUB przestrzeni. ale nie o obu w tym samym czasie. - Rocco
Złożoność zdecydowanie może dotyczyć przestrzeni. Spójrz na to: en.wikipedia.org/wiki/PSPACE - Tom Crockett
Ta odpowiedź jest najbardziej "zwykła" tutaj. Poprzednie faktycznie zakładają, że czytelnicy wiedzą wystarczająco, by je zrozumieć, ale pisarze nie są tego świadomi. Myślą, że ich są proste i proste, a absolutnie nie. Pisanie dużej ilości tekstu z ładnym formatem i tworzenie fantazyjnych sztucznych przykładów, które są trudne dla osób spoza CS, nie jest proste i proste, jest po prostu atrakcyjne dla stackoverflowers, które w większości są CS-owcami. Wyjaśnienie terminu CS w prostym języku angielskim w ogóle nie wymaga kodu i matematyki. +1 dla tej odpowiedzi, chociaż nadal nie jest wystarczająco dobry. - W.Sun
Ta odpowiedź powoduje (wspólny) błąd zakładając, że f = O (g) oznacza, że ​​f i g są proporcjonalne. - Paul Hankin