Pytanie Co dokładnie oznacza O (log n)?


Obecnie uczę się o czasach działania Big O Notation i czasach amortyzacji. Rozumiem pojęcie Na) czas liniowy, co oznacza, że ​​rozmiar wejścia wpływa proporcjonalnie na wzrost algorytmu ... i to samo dotyczy na przykład czasu kwadratowego Na2) etc ... jedne algorytmy, takie jak generatory permutacji, z Na!) razy, które rosną według silni.

Na przykład następująca funkcja to Na) ponieważ algorytm rośnie proporcjonalnie do jego wejścia n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Podobnie, gdyby istniała pętla zagnieżdżona, czas byłby równy O (n2).

Ale czym dokładnie jest O (log n)? Na przykład, co to znaczy, że wysokość pełnego drzewa binarnego jest O (log n)?

Wiem (może nie bardzo szczegółowo), czym jest Logarithm, w tym sensie, że: log10 100 = 2, ale nie mogę zrozumieć, jak zidentyfikować funkcję z logarytmicznym czasem.


1736
2018-02-21 20:05


pochodzenie


Jedno-węzłowe drzewo binarne ma wysokość log2 (1) +1 = 1, drzewo 2-węzłowe ma wysokość log2 (2) +1 = 2, drzewo 4-węzłowe ma wysokość log2 (4) +1 = 3, oraz wkrótce. Drzewo n-węzłów ma wysokość log2 (n) +1, więc dodanie węzłów do drzewa powoduje, że jego średnia wysokość rośnie logarytmicznie. - David R Tribble
Jedną z rzeczy, którą widzę w większości odpowiedzi, jest to, że zasadniczo opisują one "O (coś)", oznacza to, że czas działania algorytmu rośnie proporcjonalnie do "czegoś". Biorąc pod uwagę, że prosiłeś o "dokładne znaczenie" słowa "O (log n)", nie jest to prawdą. To intuicyjny opis notacji Big-Theta, a nie Big-O. O (log n) intuicyjnie oznacza, że ​​czas pracy rośnie najbardziej proporcjonalny do "log n": stackoverflow.com/questions/471199/... - Mehrdad Afshari
Zawsze pamiętam, jak dziel i rządź jako przykład dla O (log n) - RichardOD
Ważne jest, aby uświadomić sobie, że jego logarytm 2 (nie bazowy 10). Dzieje się tak, ponieważ na każdym etapie algorytmu usuwasz połowę pozostałych opcji. W informatyce prawie zawsze mamy do czynienia z bazą log 2, ponieważ możemy zignorować stałe. Istnieją jednak pewne wyjątki (tj. Czasy uruchamiania drzewa Quad są podstawą logu 4) - Ethan
@Ethan: Nie ma znaczenia, w jakiej bazie jesteś, ponieważ podstawowa konwersja jest tylko stałym mnożeniem, Formuła to log_b (x) = log_d (x) / log_d (b). Log_d (b) będzie po prostu stałą. - mindvirus


Odpowiedzi:


Nie mogę zrozumieć, jak zidentyfikować funkcję z czasem logowania.

Najczęstsze atrybuty logarytmicznej funkcji czasu bieżącego to:

  • wybór następnego elementu, na którym można wykonać pewne działanie, jest jedną z wielu możliwości, oraz
  • tylko jedna będzie musiała zostać wybrana.

lub

  • elementy, na których wykonywane jest działanie, to cyfry n

Dlatego na przykład wyszukiwanie osób w książce telefonicznej to O (log n). Nie musisz sprawdzać każdy osoba w książce telefonicznej, aby znaleźć właściwą; zamiast tego możesz po prostu podzielić i zdobyć, szukając w oparciu o to, gdzie ich nazwa jest alfabetyczna, aw każdej sekcji musisz tylko zbadać podzbiór każdej sekcji, zanim w końcu znajdziesz czyjś numer telefonu.

Oczywiście większa książka telefoniczna zajmie ci więcej czasu, ale nie będzie rosła tak szybko, jak proporcjonalny wzrost dodatkowego rozmiaru.


Możemy rozszerzyć przykład książki telefonicznej, aby porównać inne rodzaje operacji i ich czas pracy. Zakładamy, że nasza książka telefoniczna ma biznes ("Żółte strony"), które mają unikalne nazwy i ludzie ("Białe strony"), które mogą nie mieć unikalnych nazw. Numer telefonu jest przypisany do co najwyżej jednej osoby lub firmy. Przyjmiemy również, że przejście na określoną stronę zajmuje stały czas.

Oto czas działania niektórych operacji, które możemy wykonywać w książce telefonicznej, od najlepszych do najgorszych:

  • O (1) (najlepszy przypadek): Biorąc pod uwagę stronę, na której znajduje się nazwa firmy i nazwę firmy, znajdź numer telefonu.

  • O (1) (przeciętny przypadek): Biorąc pod uwagę stronę, na której znajduje się imię i nazwisko danej osoby, znajdź numer telefonu.

  • O (log n): Biorąc pod uwagę nazwisko osoby, znajdź numer telefonu, wybierając losowy punkt w połowie części książki, której jeszcze nie wyszukiwałeś, a następnie sprawdzając, czy nazwisko osoby znajduje się w tym miejscu. Następnie powtórz proces w połowie części książki, w której znajduje się nazwisko osoby. (Jest to binarne wyszukiwanie nazwiska osoby.)

  • Na): Znajdź wszystkie osoby, których numery telefonów zawierają cyfrę "5".

  • Na): Biorąc pod uwagę numer telefonu, znajdź osobę lub firmę o tym numerze.

  • O (n log n): W biurze drukarki było zamieszanie, a nasza książka telefoniczna zawierała wszystkie strony w losowej kolejności. Napraw uporządkowanie, aby było poprawne, patrząc na imię na każdej stronie, a następnie umieszczając tę ​​stronę w odpowiednim miejscu w nowej, pustej książce telefonicznej.

W poniższych przykładach znajdujemy się teraz w biurze drukarki. Książki telefoniczne czekają na wysłanie do każdego mieszkańca lub firmy, aw każdej książce telefonicznej znajduje się naklejka z informacją, gdzie należy je wysłać pocztą. Każda osoba lub firma otrzymuje jedną książkę telefoniczną.

  • O (n log n): Chcemy spersonalizować książkę telefoniczną, więc znajdziemy nazwisko każdej osoby lub firmy w wyznaczonej kopii, a następnie zakreślemy jej nazwisko w książce i napisamy krótką notkę z podziękowaniami za ich patronat.

  • Na2): W biurze wystąpił błąd, a każdy wpis w każdej z książek telefonicznych ma dodatkowe "0" na końcu numeru telefonu. Zrób trochę białego światła i usuń każde zero.

  • O (n · n!): Jesteśmy gotowi załadować książki telefoniczne do doku wysyłkowego. Niestety, robot, który miał załadować książki, poszedł w szał: umieszcza książki na ciężarówce w przypadkowej kolejności! Co gorsza, ładuje wszystkie książki na ciężarówkę, a następnie sprawdza, czy są w odpowiedniej kolejności, a jeśli nie, rozładowuje je i zaczyna od nowa. (To jest przerażające bogo sort.)

  • Nan): Naprawiasz robota, aby ładował wszystko poprawnie. Następnego dnia jeden z twoich współpracowników zagrał na ciebie dowcip i poprowadził robota załadunkowego do zautomatyzowanych systemów drukowania. Za każdym razem, gdy robot ładuje oryginalną książkę, drukarka fabryczna wykonuje duplikat wszystkich książek telefonicznych! Na szczęście systemy wykrywania robota robota są na tyle zaawansowane, że robot nie próbuje drukować nawet większej liczby kopii, gdy napotka duplikat książki do załadowania, ale nadal musi załadować każdą oryginalną i zduplikowaną książkę, która została wydrukowana.


2182
2018-02-21 20:14



@cletus: Zbiegiem okoliczności, obawiam się. Wybrałem to, ponieważ książki telefoniczne mają dużą literę N, ludzie rozumieją, czym są i co robią, a ponieważ są uniwersalne jako przykład. Poza tym w moich wyjaśnieniach muszę używać robotów! Wygrana dookoła. (Wygląda na to, że twoja odpowiedź została złożona, zanim jeszcze zostałem członkiem na StackOverflow!) - John Feminella
"W biurze wystąpił błąd, a każdy wpis w każdej z książek telefonicznych ma dodatkowe" 0 "na końcu numeru telefonu. Usuń trochę białych i usuń każde zero." <- To nie jest kolejność N do kwadratu. N jest definiowane jako wielkość danych wejściowych. Rozmiar danych wejściowych to liczba numerów telefonów, czyli liczba numerów na książkę, która jest razy większa od liczby książek. To wciąż liniowa operacja czasu. - Billy ONeal
@Billy: w tym przykładzie N to liczba osób w jednej książce. Ponieważ każda osoba w książce telefonicznej otrzymuje także własną kopię książki, są N  identyczny książki telefoniczne, każda z nich N ludzie w nim, czyli O (N ^ 2). - John Feminella
Czy nie jest O (1) najlepszym przypadkiem, a nie najgorszym przypadkiem, ponieważ jest on dziwnie podkreślony jako? - Svip
Zajęło mi O (long⅝n! N-55/2) czas, aby znaleźć definicję O (log n), która ostatecznie ma sens. +1 - iAteABug_And_iLiked_it


Wiele dobrych odpowiedzi zostało już zaksięgowanych na to pytanie, ale uważam, że naprawdę brakuje nam ważnego - a mianowicie ilustrowanej odpowiedzi.

Co to znaczy powiedzieć, że wysokość pełnego drzewa binarnego to O (log n)?

Poniższy rysunek przedstawia drzewo binarne. Zauważ, że każdy poziom zawiera podwójną liczbę węzłów w porównaniu do poziomu powyżej (stąd dwójkowy):

Binary tree

Wyszukiwanie binarne jest przykładem złożonym O(log n). Powiedzmy, że węzły na dolnym poziomie drzewa na rysunku 1 reprezentują elementy w jakiejś posortowanej kolekcji. Wyszukiwanie binarne jest algorytmem dziel i zdobądź, a rysunek pokazuje, w jaki sposób będziemy potrzebować (maksymalnie) 4 porównania, aby znaleźć rekord, którego szukamy w tym zbiorze danych 16 pozycji.

Załóżmy, że zamiast tego mamy zbiór danych z 32 elementami. Kontynuuj powyższy rysunek, aby przekonać się, że będziemy potrzebować 5 porównań, aby znaleźć to, czego szukamy, ponieważ drzewo zwiększyło się o jeden poziom głębiej, gdy pomnożyliśmy ilość danych. W rezultacie złożoność algorytmu można opisać jako porządek logarytmiczny.

Konspiratorstwo log(n) na zwykłej kartce papieru spowoduje wykres, w którym wzrost krzywej maleje jako n wzrasta:

O(log n)


510
2018-02-21 22:22



"Zauważ, jak każdy poziom zawiera podwójną liczbę węzłów w porównaniu do poziomu powyżej (stąd binarny)" To jest nieprawidłowe. To, co opisujesz, to zrównoważony drzewo binarne. Drzewo binarne oznacza po prostu, że każdy węzeł ma co najwyżej dwoje dzieci. - Oenotria
W rzeczywistości jest to bardzo wyważone drzewo binarne, zwane pełnym drzewem binarnym. Edytowałem odpowiedź, ale potrzebuję kogoś, kto ją zatwierdzi. - user21820
Pełne drzewo binarne nie musi mieć całkowitego wypełnienia ostatniego poziomu. Powiedziałbym, że bardziej odpowiednie jest "pełne drzewo binarne". - Mr. AJ
Twoja odpowiedź próbuje konkretniej odpowiedzieć na pierwotny problem PO, więc jest lepsza niż obecna zaakceptowana odpowiedź (IMO), ale wciąż jest bardzo niekompletna: podajesz tylko połowiczny przykład i dwa obrazy ... - nbro
To drzewo ma 31 elementów, a nie 16. Dlaczego jest to zestaw danych o 16 elementach? Każdy węzeł na nim reprezentuje liczbę, w przeciwnym razie byłoby to nieefektywne drzewo binarne: P - Perry Monschau


O(log N) zasadniczo oznacza, że ​​czas rośnie liniowo, podczas gdy n rośnie wykładniczo. Więc jeśli to zajmie 1 drugi do obliczenia 10 elementy, to zajmie 2 sekundy do obliczenia 100 elementy, 3 sekundy do obliczenia 1000 elementy i tak dalej.

Tak jest O(log n) kiedy dzielimy i pokonujemy algorytmy, np. wyszukiwanie binarne. Innym przykładem jest szybkie sortowanie, gdzie za każdym razem dzielimy tablicę na dwie części i za każdym razem O(N) czas znaleźć element przestawny. Stąd to N O(log N) 


464
2018-02-21 20:18



Trzy linijki mądrości, które biją wszystkie inne odpowiedzi na esej ... :) Na wypadek, gdyby ktoś go przegapił, w kontekście programowania baza logu to 2 (nie 10), więc O (log n) skaluje się jak 1 sekunda na 10 elementy, 2 sekundy na 20, 3 na 40 itd. - nawfal
Uzgodnione, zwięzłe i jasne, chociaż kończącym się pytaniem z PO było, jak zidentyfikować funkcję logarytmiczną, nie do końca "co to jest" - Adam
tak, funkcja logarytmiczna jest odwrotna do funkcji wykładniczej. ((log x) podstawa a) jest odwrotnością (moc x). Analiza jakościowa tych funkcji za pomocą wykresów dałaby więcej intuicji. - overexchange
Zajęło mi to około 3 read-throughs, aby zrozumieć, że nie było źle. Czas idzie liniowo, podczas gdy liczba elementów jest wykładniczy. To znaczy więcej elementów w krótszym czasie. To jest mentalne opodatkowanie dla tych, którzy wizualizują log jako znajomą krzywą logu na wykresie. - Qix
Myślę, że jest to bardzo dobra odpowiedź, z wyjątkiem części, w której twierdzi, że wyszukiwanie binarne jest algorytmem dziel i podbijaj. Nie jest. - code_dredd


Poniższe wyjaśnienie odnosi się do przypadku w pełni zrównoważony drzewo binarne, które pomoże ci zrozumieć, w jaki sposób uzyskujemy logarytmiczną złożoność czasu.

Drzewo binarne to przypadek, w którym problem rozmiaru n jest podzielony na pod-problem wielkości n / 2, dopóki nie osiągniemy problemu o wielkości 1:

height of a binary tree

W ten sposób otrzymujesz O (log n), który jest ilością pracy, którą należy wykonać na powyższym drzewie, aby osiągnąć rozwiązanie.

Wspólnym algorytmem o złożoności czasu O (log n) jest wyszukiwanie binarne, którego relacja rekurencyjna to T (n / 2) + O (1), tj. Na każdym kolejnym poziomie drzewa dzielisz problem na pół i wykonujesz stałą ilość dodatkowej pracy.


198
2017-10-26 19:33



nowicjusz tutaj. Czy możesz powiedzieć, że wysokość drzewa to współczynnik dzielenia przez rekursję do osiągnięcia rozmiaru n = 1? - Cody


Jeśli masz funkcję, która bierze:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Potem loguje2(n) czas. The Big O notationluźno mówiąc oznacza, że ​​związek musi być prawdziwy tylko dla dużych n, i że stałe czynniki i mniejsze terminy mogą być ignorowane.


121
2018-02-21 20:11



to log2 (n) jest takie samo jak o (log n)? - Sven van den Boogaart
Tak, patrz komentarz przez nawfal dla innej odpowiedzi tutaj: (kopiowanie-wklejanie) - w kontekście programowania baza logu to 2 (nie 10), więc O (log n) skaluje się jak 1 sekunda dla 10 elementów, 2 sekundy dla 20 , 3 za 40 itd - Andrejs


Przegląd

Inne dały dobre przykłady diagramów, takie jak diagramy drzew. Nie widziałem żadnych prostych przykładów kodu. Tak więc, oprócz moich wyjaśnień, przedstawię niektóre algorytmy za pomocą prostych instrukcji drukowania, aby zilustrować złożoność różnych kategorii algorytmów.

Najpierw będziesz chciał mieć ogólne pojęcie Logarithm, z którego możesz korzystać https://en.wikipedia.org/wiki/Logarithm . Korzystanie z nauk przyrodniczych e i dziennik naturalny. Inżynierowie będą używać log_10 (log base 10), a informatycy będą używać log_2 (log base 2), ponieważ komputery są oparte na binarnych. Czasami zobaczysz skróty logu naturalnego jako ln()inżynierowie zwykle wyłączają _10 i po prostu używają log() a log_2 jest skracany jako lg(). Wszystkie typy logarytmów rosną w podobny sposób, dlatego mają tę samą kategorię log(n).

Kiedy spojrzysz na przykłady kodu poniżej, polecam spojrzenie na O (1), następnie O (n), następnie O (n ^ 2). Po tym jak jesteś z nimi dobry, spójrz na pozostałe. Dodałem czyste przykłady i odmiany, aby pokazać, jak subtelne zmiany mogą nadal powodować tę samą kategoryzację.

Możesz myśleć o O (1), O (n), O (logn), itp. Jako klasach lub kategoriach wzrostu. Niektóre kategorie wymagają więcej czasu niż inne. Te kategorie pomagają nam w sposobie zamawiania działania algorytmu. Niektóre z nich rozwijały się szybciej, gdy n wejściowy rośnie. Poniższa tabela pokazuje liczbowy wzrost. W poniższej tabeli jest log (n) jako pułap log_2.

enter image description here

Proste przykłady kodów różnych dużych kategorii O:

O (1) - Przykłady stałego czasu:

  • Algorytm 1:

Algorytm 1 drukuje cześć raz i nie zależy od n, więc zawsze będzie działał w stałym czasie, więc tak jest O(1).

print "hello";
  • Algorytm 2:

Algorytm 2 drukuje cześć 3 razy, jednak nie zależy od wielkości wejściowej. Nawet gdy rośnie, ten algorytm zawsze drukuje tylko trzy razy. Mówiąc 3, jest stała, więc ten algorytm również jest O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Przykłady logarytmiczne:

  • Algorytm 3 - Działa to jak "log_2"

Algorytm 3 pokazuje algorytm, który działa w log_2 (n). Zauważ, że po operacji pętli for zwielokrotnia bieżącą wartość i o 2, czyli i przechodzi od 1 do 2 do 4 do 8 do 16 do 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algorytm 4 - Działa to jak "log_3"

Algorytm 4 pokazuje log_3. Ogłoszenie i przechodzi od 1 do 3 do 9 do 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algorytm 5 - Działa to jak "log_1.02"

Algorytm 5 jest ważny, ponieważ pomaga pokazać, że tak długo, jak liczba jest większa niż 1, a wynik jest wielokrotnie mnożony względem siebie, że patrzysz na algorytm logarytmiczny.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Przykłady liniowe:

  • Algorytm 6

Ten algorytm jest prosty, który drukuje cześć razy.

for(int i = 0; i < n; i++)
  print "hello";
  • Algorytm 7

Ten algorytm pokazuje odmianę, w której wydrukuje się ją n / 2 razy. n / 2 = 1/2 * n. Ignorujemy stałą 1/2 i widzimy, że ten algorytm to O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Przykłady:

  • Algorytm 8

Pomyśl o tym jako o kombinacji O(log(n)) i O(n). Zagnieżdżanie pętli for pomaga nam uzyskać O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algorytm 9

Algorytm 9 jest podobny do algorytmu 8, ale każda z pętli zezwala na zmiany, które nadal skutkują końcowym wynikiem O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n kwadrat Przykłady:

  • Algorytm 10

O(n^2) uzyskuje się łatwo przez zagnieżdżanie standardu dla pętli.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algorytm 11

Podobnie jak algorytm 10, ale z pewnymi odmianami.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubed Przykłady:

  • Algorytm 12

To jest jak algorytm 10, ale z 3 pętlami zamiast 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algorytm 13

Podobnie jak algorytm 12, ale z pewnymi odmianami, które wciąż dają O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Podsumowanie

Powyższe przykłady przedstawiają kilka prostych przykładów i wariantów, które pomagają zademonstrować, jakie subtelne zmiany można wprowadzić, które tak naprawdę nie zmieniają analizy. Mam nadzieję, że daje wystarczająco dużo wglądu.


108
2018-04-26 22:50



Niesamowite. Najlepsze wytłumaczenie dla mnie, jakie widziałem. Byłoby fajniej, gdyby O(n^2) jest odnotowany jako połączenie O(n) i O(n), więc O(n) * O(n) = O(n * n) = O(n^2). Wydaje się, że trochę skacząc bez tego równania. Jest to powtórzenie wcześniejszych wyjaśnień, ale myślę, że to powtórzenie może zapewnić czytelnikom większą pewność w zrozumieniu. - Eonil
@james dziękuje za niesamowite odpowiedzi - Asthme
To jest po prostu najlepsze wytłumaczenie. - Edgar Kiljak


Logarytmiczny czas działania (O(log n)) zasadniczo oznacza, że ​​czas pracy rośnie proporcjonalnie do logarytm rozmiaru wejściowego - na przykład, jeśli 10 elementów zajmuje co najwyżej trochę czasu x, a 100 przedmiotów zajmuje co najwyżej, powiedzmy, 2x, a 10 000 elementów zajmuje co najwyżej 4x, to wygląda jak O(log n) złożoność czasu.


84
2018-02-21 20:10



log2 lub log10 są nieistotne. Różnią się one tylko współczynnikiem skali, który sprawia, że ​​są one tego samego rzędu, tj. Nadal rosną w tym samym tempie. - Noldorin
Fajną rzeczą w logarytmach jest to, że porównując względne wysokości, dokładna baza, której używasz, nie ma znaczenia. log 10,000 / log 100 to 2 niezależnie od tego, z jakiej bazy korzystasz. - Anon.
Aby być nędznym, O (lg n) oznacza, że ​​jest to środowisko wykonawcze najbardziej proporcjonalny do lg n. To, co opisujesz, to Theta (lg n).
@grgrig: To prawda. Edytowałem w kilku "co najwyżej", aby wskazać górny charakter big-O. - Anon.
@grgrig opisał zarówno O jak i theta: Theta (lg n) oznacza O (lg n) - klochner