Co dokładnie oznacza O (log n)?

Uczę się o czasach działania i czasach amortyzacji Big O Notation. Rozumiem pojęcie czasu liniowego O (n) , co oznacza, że ​​rozmiar danych wejściowych wpływa proporcjonalnie na wzrost algorytmu ... to samo dotyczy na przykład czasu kwadratowego O (n ² ) itd. Nawet algorytmy , takie jak generatory permutacji, z czasami O (n!) , które rosną silnie.

Na przykład następującą funkcją jest O (n), ponieważ algorytm rośnie proporcjonalnie do swojego wejścia n :

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

Podobnie, jeśli istnieje zagnieżdżona pętla, czas będzie wynosił O (n ² ).

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

Wiem (może nie bardzo szczegółowo), czym jest Logarytm, w tym sensie, że: log ₁₀ 100 = 2, ale nie rozumiem, jak rozpoznać funkcję z czasem logarytmicznym.

Nie rozumiem, jak zidentyfikować funkcję z czasem dziennika.

Najczęstsze atrybuty logarytmicznej funkcji czasu działania to:

• wybór następnego elementu, na którym należy wykonać jakąś akcję, jest jedną z kilku możliwości, oraz
• tylko jeden będzie musiał zostać wybrany.

lub

• elementy, na których wykonywana jest akcja, to cyfry n

Dlatego na przykład wyszukiwanie osób w książce telefonicznej to O (log n). Nie musisz sprawdzać każdej osoby w książce telefonicznej, aby znaleźć właściwą; zamiast tego możesz po prostu dzielić i podbijać, patrząc na podstawie alfabetu ich nazwy, aw każdej sekcji wystarczy przejrzeć podzbiór każdej sekcji, zanim w końcu znajdziesz czyjś numer telefonu.

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

Możemy rozwinąć przykład książki telefonicznej, aby porównać inne rodzaje operacji i ich czas działania. Zakładamy, że nasza książka telefoniczna zawiera firmy („Żółte strony”), które mają unikalne nazwy i osoby („Białe strony”), które mogą nie mieć unikalnych nazw. Numer telefonu jest przypisany maksymalnie jednej osobie lub firmie. Zakładamy również, że przejście do określonej strony zajmuje cały czas.

Oto czasy wykonywania niektórych operacji, które możemy wykonać w książce telefonicznej, od najszybszych do najwolniejszych:

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

• O (1) (w przeciętnym przypadku): Biorąc pod uwagę stronę, na której znajduje się nazwisko osoby i jej nazwisko, znajdź numer telefonu.

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

• O (n): Znajdź wszystkie osoby, których numery telefonów zawierają cyfrę „5”.

• O (n): Znając numer telefonu, znajdź osobę lub firmę o tym numerze.

• O (n log n): W biurze drukarki doszło do pomyłki, a wszystkie nasze książki telefoniczne zostały wstawione w losowej kolejności. Napraw kolejność, aby była poprawna, patrząc na imię na każdej stronie, a następnie umieszczając tę ​​stronę w odpowiednim miejscu w nowej, pustej książce telefonicznej.

Dla poniższych przykładów jesteśmy teraz w biurze drukarki. Książki telefoniczne czekają na wysłanie do każdego mieszkańca lub firmy, a na każdej książce telefonicznej znajduje się naklejka z informacją, gdzie należy ją wysłać. Każda osoba lub firma otrzymuje jedną książkę telefoniczną.

• O (n log n): Chcemy spersonalizować książkę telefoniczną, dlatego znajdziemy nazwisko każdej osoby lub firmy w wyznaczonym egzemplarzu, a następnie zakreślimy ich nazwisko w książce i napiszemy krótką notatkę z podziękowaniami za ich patronat .

• O (n ² ): Wystąpił błąd w biurze, a każdy wpis w każdej książce telefonicznej ma dodatkowe „0” na końcu numeru telefonu. Weź trochę bieli i usuń każde zero.

• O (n · n!): Jesteśmy gotowi załadować książki telefoniczne do stacji dokującej. Niestety robot, który miał załadować książki, wpadł w szaleństwo: układa książki na ciężarówce w losowej 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 przerażający rodzaj bogo .)

• O (n ⁿ ): Naprawiasz robota, aby ładował wszystko poprawnie. Następnego dnia jeden z twoich współpracowników robi ci psikus i podłącza robota dokującego do zautomatyzowanych systemów drukowania. Za każdym razem, gdy robot ładuje oryginalną książkę, drukarka fabryczna wykonuje kopię wszystkich książek telefonicznych! Na szczęście systemy wykrywania błędów robota są na tyle zaawansowane, że robot nie próbuje wydrukować jeszcze większej liczby kopii, gdy napotka zduplikowaną książkę do załadowania, ale nadal musi załadować każdą oryginalną i zduplikowaną książkę, która została wydrukowana.

O(log N)w zasadzie oznacza, że ​​czas płynie liniowo, a nrośnie wykładniczo. Więc jeśli trwa 1drugi do obliczania 10elementów, to zajmie 2sekund do obliczania 100elementów, 3sekund do obliczania 1000elementów, i tak dalej.

To O(log n)wtedy dzielimy i podbijamy algorytmy typu, np. Wyszukiwanie binarne. Innym przykładem jest szybkie sortowanie, w którym za każdym razem dzielimy tablicę na dwie części i za każdym razem, O(N)gdy znalezienie elementu przestawnego zajmuje trochę czasu. Stąd to N O(log N)

Na to pytanie zostało już napisanych wiele dobrych odpowiedzi, ale uważam, że naprawdę brakuje nam ważnej - mianowicie ilustrowanej odpowiedzi.

Co to znaczy powiedzieć, że wysokość pełnego drzewa binarnego wynosi 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 binarny ):

Wyszukiwanie binarne jest przykładem o złożoności O(log n). Powiedzmy, że węzły na dolnym poziomie drzewa na rysunku 1 reprezentują elementy z jakiejś posortowanej kolekcji. Wyszukiwanie binarne jest algorytmem dziel i zwyciężaj, a rysunek pokazuje, jak potrzebujemy (co najwyżej) 4 porównań, aby znaleźć rekord, którego szukamy w tym zestawie danych z 16 pozycji.

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

Wykreślenie log(n)na zwykłym kawałku papieru spowoduje powstanie wykresu, na którym wzrost krzywej spowalnia wraz ze nwzrostem:

W poniższym wyjaśnieniu wykorzystano przypadek w pełni zbalansowanego drzewa binarnego, aby pomóc ci zrozumieć, w jaki sposób uzyskujemy logarytmiczną złożoność czasu.

Drzewo binarne to przypadek, w którym problem o rozmiarze n dzieli się na podproblem o rozmiarze n / 2, dopóki nie osiągniemy problemu o rozmiarze 1:

I tak otrzymujesz O (log n), czyli ilość pracy, którą należy wykonać na powyższym drzewie, aby znaleźć rozwiązanie.

Częstym algorytmem o złożoności czasowej O (log n) jest Wyszukiwanie Binarne, którego relacją rekurencyjną jest T (n / 2) + O (1), tj. Na każdym kolejnym poziomie drzewa dzielisz problem na pół i wykonujesz stałą ilość dodatkowej pracy.

Przegląd

Inni podali dobre przykłady diagramów, takie jak diagramy drzewiaste. Nie widziałem żadnych prostych przykładów kodu. Oprócz mojego wyjaśnienia przedstawię kilka algorytmów z prostymi instrukcjami drukowania, aby zilustrować złożoność różnych kategorii algorytmów.

Po pierwsze, będziesz chciał mieć ogólne pojęcie o logarytmie, które możesz uzyskać na stronie https://en.wikipedia.org/wiki/Logarithm . Zastosowanie w naukach przyrodniczych ei dziennik naturalny. Uczniowie inżynierii używają log_10 (log log base 10), a informatycy często używają log_2 (log base 2), ponieważ komputery są binarne. Czasami zobaczysz skróty logu naturalnego, ponieważ ln()inżynierowie zwykle wyłączają _10 i po prostu używają, log()a log_2 to skrót lg(). Wszystkie rodzaje logarytmów rosną w podobny sposób, dlatego dzielą tę samą kategorię log(n).

Gdy spojrzysz na poniższe przykłady kodu, polecam przyjrzenie się O (1), następnie O (n), a następnie O (n ^ 2). Kiedy będziesz z nimi dobry, spójrz na innych. Podałem czyste przykłady, a także odmiany, aby zademonstrować, jak subtelne zmiany mogą nadal prowadzić do tej samej kategoryzacji.

Możesz myśleć o O (1), O (n), O (logn) itp. Jako klasach lub kategoriach wzrostu. Niektóre kategorie zajmą więcej czasu niż inne. Te kategorie pomagają nam uporządkować wydajność algorytmu. Niektóre rosły szybciej wraz ze wzrostem wartości wejściowej n. Poniższa tabela pokazuje wspomniany wzrost liczbowo. W poniższej tabeli traktuj log (n) jako pułap log_2.

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

O (1) - Przykłady stałych czasów:

• Algorytm 1:

Algorytm 1 wypisuje 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 to od wielkości wejściowej. Nawet gdy rośnie n, ten algorytm zawsze drukuje tylko cześć 3 razy. To powiedziawszy 3, jest stałą, więc ten algorytm też O(1).

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

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

• Algorytm 3 - Działa jak „log_2”

Algorytm 3 pokazuje algorytm działający w log_2 (n). Zauważ, że operacja końcowa pętli for zwielokrotnia bieżącą wartość i przez 2, więc izmienia się 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 jak „log_3”

Algorytm 4 pokazuje log_3. Uwaga izmienia się z 1 na 3 na 9 na 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algorytm 5 - Działa jak „log_1.02”

Algorytm 5 jest ważny, ponieważ pomaga pokazać, że dopóki liczba jest większa niż 1, a wynik jest wielokrotnie mnożony względem siebie, patrzysz na algorytm logarytmiczny.

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

O (n) - Przykłady czasu liniowego:

• Algorytm 6

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

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

• Algorytm 7

Ten algorytm pokazuje odmianę, w której wypisze cześć 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 połączeniu 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 dopuszcza wariacje, które nadal powodują, że końcowy wynik jest 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 do kwadratu Przykłady:

• Algorytm 10

O(n^2) można łatwo uzyskać poprzez zagnieżdżenie standardu dla pętli.

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

• Algorytm 11

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 pokrojone w kostkę 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

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żej podano kilka prostych przykładów i odmian, aby pokazać, jakie subtelne zmiany można wprowadzić, które tak naprawdę nie zmieniają analizy. Mam nadzieję, że daje to wystarczającą wiedzę.

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 zajmuje to czas log ₂ (n). Notacji Big O , luźno mówiąc, oznacza, że tylko związek musi być prawdziwe dla dużych n, i że czynniki stałe i mniejsze terminy mogą być ignorowane.

Logarytmiczny czas działania ( O(log n)) zasadniczo oznacza, że ​​czas działania rośnie proporcjonalnie do logarytmu wielkości wejściowej - na przykład, jeśli 10 elementów zajmuje najwyżej pewien czas x, a 100 elementów zajmuje, powiedzmy 2x, i 10 000 elementów zajmuje najwyżej 4x, to wygląda na O(log n)złożoność czasu.

Logarytm

Ok, spróbujmy w pełni zrozumieć, czym jest logarytm.

Wyobraź sobie, że mamy linę i przywiązaliśmy ją do konia. Jeśli lina jest bezpośrednio przywiązana do konia, siła, którą koń musiałby odciągnąć (powiedzmy od człowieka), wynosi bezpośrednio 1.

Teraz wyobraź sobie, że lina jest owinięta wokół słupa. Koń, który chce uciec, będzie musiał wielokrotnie ciągnąć mocniej. Ilość razy będzie zależeć od szorstkości liny i wielkości słupa, ale załóżmy, że zwiększy ona siłę przez 10 (gdy lina wykona pełny obrót).

Teraz, jeśli lina zostanie zapętlona raz, koń będzie musiał pociągnąć 10 razy mocniej. Jeśli człowiek zdecyduje się naprawdę utrudnić koniowi, może ponownie owinąć linę wokół słupa, zwiększając jej siłę o dodatkowe 10 razy. Trzecia pętla ponownie zwiększy siłę o kolejne 10 razy.

Widzimy, że dla każdej pętli wartość wzrasta o 10. Liczba zwojów wymaganych do uzyskania dowolnej liczby nazywana jest logarytmem liczby, tzn. Potrzebujemy 3 słupków, aby pomnożyć siłę przez 1000 razy, 6 słupków, aby pomnożyć siłę przez 1 000 000

3 to logarytm 1 000, a 6 to logarytm 1 000 000 (podstawa 10).

Co zatem oznacza O (log n)?

W powyższym przykładzie naszą „stopą wzrostu” jest O (log n) . Dla każdej dodatkowej pętli siła, którą może wytrzymać nasza lina, jest 10 razy większa:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Teraz w powyższym przykładzie użyto podstawy 10, ale na szczęście podstawa dziennika jest nieznaczna, gdy mówimy o dużej notacji.

Teraz wyobraźmy sobie, że próbujesz odgadnąć liczbę od 1 do 100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Teraz zajęło Ci 7 domysłów, aby to zrobić dobrze. Ale jaki jest tutaj związek? Jaką liczbę przedmiotów możesz odgadnąć na podstawie każdego dodatkowego odgadnięcia?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Korzystając z wykresu, możemy zobaczyć, że jeśli użyjemy wyszukiwania binarnego do odgadnięcia liczby od 1 do 100, zajmie nam to co najwyżej 7 prób. Gdybyśmy mieli 128 liczb, moglibyśmy również odgadnąć liczbę w 7 próbach, ale 129 liczb zajmie nam co najwyżej 8 prób (w odniesieniu do logarytmów, tutaj potrzebowalibyśmy 7 domysłów dla zakresu wartości 128, 10 domysłów dla zakresu wartości 1024 . 7 to logarytm równy 128, 10 to logarytm równy 1024 (podstawa 2).

Zauważ, że pogrubiłem „co najwyżej”. Notacja Big-O zawsze odnosi się do gorszego przypadku. Jeśli masz szczęście, możesz odgadnąć liczbę za jednym razem, więc najlepszym przypadkiem jest O (1), ale to już inna historia.

Widzimy, że za każdym razem nasz zestaw danych się kurczy. Dobrą zasadą pozwalającą ustalić, czy algorytm ma czas logarytmiczny, jest sprawdzenie, czy zestaw danych zmniejsza się o określoną kolejność po każdej iteracji

Co z O (n log n)?

W końcu natkniesz się na algorytm czasu liniowego O (n log (n)) . Powyższa zasada obowiązuje ponownie, ale tym razem funkcja logarytmiczna musi działać n razy, np. Zmniejszając rozmiar listy n razy , co występuje w algorytmach takich jak scalanie.

Możesz łatwo określić, czy czas algorytmu wynosi n log n. Poszukaj zewnętrznej pętli, która iteruje przez listę (O (n)). Następnie sprawdź, czy istnieje pętla wewnętrzna. Jeśli wewnętrzna pętla wycina / zmniejsza zestaw danych przy każdej iteracji, to ta pętla to (O (log n)), więc ogólny algorytm to = O (n log n) .

Zrzeczenie się: Przykład logarytmów linowych został zaczerpnięty z doskonałej książki Mathematician's Delight autorstwa W.Sawyer .

Możesz myśleć o O (log N) intuicyjnie, mówiąc, że czas jest proporcjonalny do liczby cyfr w N.

Jeśli operacja wykonuje stałą pracę czasową dla każdej cyfry lub bitu wejścia, cała operacja zajmie czas proporcjonalny do liczby cyfr lub bitów na wejściu, a nie wielkości wejścia; zatem O (log N) zamiast O (N).

Jeśli operacja podejmie serię decyzji o stałym czasie, z których każda o połowę (zmniejsza o 3, 4, 5 ..) wielkość danych wejściowych do rozważenia, całość zajmie czas proporcjonalny do logarytmicznej podstawy 2 (podstawa 3 , podstawa 4, podstawa 5 ...) o wielkości N danych wejściowych, a nie O (N).

I tak dalej.

Najlepszy sposób, w jaki zawsze musiałem wizualizować mentalnie algorytm działający w O (log n), jest następujący:

Jeśli zwiększysz rozmiar problemu przez pomnożenie kwoty (tj. Pomnożenie jego rozmiaru przez 10), praca zostanie zwiększona tylko o kwotę addytywną.

Zastosuj to do pytania o drzewo binarne, abyś miał dobrą aplikację: jeśli podwoisz liczbę węzłów w drzewie binarnym, wysokość wzrośnie tylko o 1 (kwota addytywna). Jeśli podwoisz to jeszcze raz, to wciąż wzrośnie tylko o 1. (Oczywiście zakładam, że pozostaje zrównoważony i tak dalej). W ten sposób, zamiast podwoić swoją pracę, gdy rozmiar problemu jest pomnożony, wykonujesz tylko nieznacznie więcej pracy. Właśnie dlatego algorytmy O (log n) są niesamowite.

Najpierw polecam przeczytać następującą książkę;

Algorytmy (wydanie 4)

Oto niektóre funkcje i ich oczekiwane złożoności. Liczby wskazują częstotliwości wykonywania instrukcji .

Po wykresie złożoności Big-O również wzięty z bigocheatsheet

Na koniec bardzo prosta prezentacja pokazuje, w jaki sposób jest obliczana;

Anatomia częstotliwości wykonywania instrukcji programu.

Analiza czasu działania programu (przykład).

Co to jest log _b (n)?

Jest to liczba przypadków, w których możesz wielokrotnie pociąć dziennik długości n na b równych części, zanim osiągniesz odcinek o rozmiarze 1.

Algorytmy dzielenia i zdobywania mają zwykle lognkomponent czasu działania. Wynika to z powtarzanej połowy wejścia.

W przypadku wyszukiwania binarnego każda iteracja wyrzuca połowę danych wejściowych. Należy zauważyć, że w notacji Big-O log jest bazą log 2.

Edycja: Jak już wspomniano, podstawa logu nie ma znaczenia, ale podczas wyprowadzania wydajności algorytmu Big-O współczynnik logarytmu będzie pochodził ze zmniejszenia o połowę, dlatego myślę o tym jako o podstawie 2.

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

Sformułowałbym to, ponieważ „wysokość pełnego drzewa binarnego to log n”. Obliczenie wysokości pełnego drzewa binarnego byłoby O (log n), gdybyś przechodził krok po kroku.

Nie rozumiem, jak zidentyfikować funkcję z czasem logarytmicznym.

Logarytm jest zasadniczo odwrotnością potęgowania. Zatem jeśli każdy „krok” funkcji eliminuje czynnik elementów z oryginalnego zestawu elementów, jest to logarytmiczny algorytm czasu.

Na przykład drzewa można łatwo zauważyć, że obniżenie poziomu węzłów zmniejsza wykładniczą liczbę elementów w miarę kontynuowania przemierzania. Popularny przykład przeglądania książki telefonicznej posortowanej według nazwisk jest zasadniczo równoważny przeglądaniu drzewa wyszukiwania binarnego (środkowa strona jest elementem głównym i na każdym kroku można wydedukować, czy przejść w lewo, czy w prawo).

Te 2 przypadki zajmą czas O (log n)

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) jest nieco mylące, a dokładniej O (log ₂ n), tj. (Logarytm z bazą 2).

Wysokość zbalansowanego drzewa binarnego wynosi O (log ₂ n), ponieważ każdy węzeł ma dwa (zwróć uwagę na „dwa” jak w log ₂ n) węzły potomne. Zatem drzewo z n węzłami ma wysokość log ₂ n.

Innym przykładem jest wyszukiwanie binarne, które ma czas działania O (log ₂ n), ponieważ na każdym kroku dzielisz przestrzeń wyszukiwania przez 2.

O(log n) odnosi się do funkcji (lub algorytmu lub kroku w algorytmie) działającej w czasie proporcjonalnym do logarytmu (zwykle podstawa 2 w większości przypadków, ale nie zawsze, a w każdym razie jest to nieistotne w notacji wielkiej-O *) wielkości wejścia.

Funkcja logarytmiczna jest odwrotnością funkcji wykładniczej. Innymi słowy, jeśli dane wejściowe rosną wykładniczo (a nie liniowo, jak zwykle by się to wydawało), funkcja rośnie liniowo.

O(log n)czasy uruchamiania są bardzo powszechne w każdym rodzaju aplikacji dziel i zwyciężaj, ponieważ (idealnie) za każdym razem redukujesz pracę o połowę. Jeśli na każdym z etapów podziału lub podboju wykonujesz stałą pracę (lub pracę, która nie jest stała, ale z czasem rośnie wolniej niż O(log n)), to cała twoja funkcja jest O(log n). Dość często zdarza się, że każdy krok wymaga liniowego czasu na wejściu; będzie to stanowić całkowitą złożoność czasu wynoszącą O(n log n).

Złożoność wyszukiwania binarnego w czasie wykonywania jest przykładem O(log n). Dzieje się tak, ponieważ w wyszukiwaniu binarnym zawsze ignorujesz połowę danych wejściowych na każdym kolejnym etapie, dzieląc tablicę na pół i skupiając się tylko na połowie z każdym krokiem. Każdy krok ma charakter stały, ponieważ w wyszukiwaniu binarnym wystarczy porównać tylko jeden element z kluczem, aby dowiedzieć się, co robić dalej bez względu na to, jak duża jest rozważana tablica w dowolnym momencie. Więc wykonujesz około log (n) / log (2) kroków.

Złożoność podczas sortowania metodą scalania jest przykładem O(n log n). Dzieje się tak, ponieważ dzielisz tablicę na pół z każdym krokiem, co daje w sumie około log (n) / log (2) kroków. Jednak na każdym etapie należy wykonać operacje scalania na wszystkich elementach (niezależnie od tego, czy jest to jedna operacja scalania na dwóch podlistach elementów n / 2, czy dwie operacje scalania na czterech podlistach elementów n / 4, nie ma znaczenia, ponieważ zwiększa konieczność zrób to dla n elementów na każdym kroku). Zatem całkowita złożoność wynosi O(n log n).

* Pamiętaj, że notacja big-O, z definicji , stałe nie mają znaczenia. Również przez zmianę reguły podstawowej dla logarytmów jedyną różnicą między logarytmami różnych zasad jest czynnik stały.

Oznacza to po prostu, że czas potrzebny na to zadanie rośnie z log (n) (przykład: 2s dla n = 10, 4s dla n = 100, ...). Przeczytaj artykuły w Wikipedii na temat algorytmu wyszukiwania binarnego i notacji Big O, aby uzyskać więcej szczegółów.

Mówiąc prosto: na każdym etapie algorytmu możesz przeciąć pracę na pół. (Asymptotycznie równoważne do trzeciego, czwartego, ...)

Jeśli narysujesz funkcję logarytmiczną na kalkulatorze graficznym lub czymś podobnym, zobaczysz, że rośnie ona bardzo powoli - nawet wolniej niż funkcja liniowa.

Właśnie dlatego algorytmy o logarytmicznej złożoności czasowej są bardzo poszukiwane: nawet dla naprawdę dużego n (powiedzmy na przykład n = 10 ^ 8) działają one bardziej niż akceptowalnie.

Ale czym dokładnie jest O (log n)

To, co dokładnie znaczy, to „jak nzmierza w kierunku infinity, timedąży do tego, a*log(n)gdzie ajest stały współczynnik skalowania”.

A właściwie to wcale nie znaczy; bardziej prawdopodobne, że oznacza to coś w rodzaju „ timepodzielone przez a*log(n)tendencje w kierunku 1”.

„Tendencja do” ma zwykłe matematyczne znaczenie z „analizy”: na przykład, że „jeśli wybierzesz dowolną dowolną stałą niezerową k, wtedy mogę znaleźć odpowiednią wartość Xtaką, która ((time/(a*log(n))) - 1)jest mniejsza niż kdla wszystkich wartości nwiększych niż X”.

Mówiąc w skrócie, oznacza to, że równanie czasu może zawierać inne elementy: np. Może mieć pewien stały czas uruchamiania; ale te inne składniki bledną w kierunku nieistotności dla dużych wartości n, a a * log (n) jest dominującym terminem dla dużej n.

Zauważ, że gdyby równanie było na przykład ...

czas (n) = a + b log (n) + c n + d n n

... wtedy byłoby to O (n do kwadratu), ponieważ bez względu na wartości stałych a, b, c i niezerowe d, d*n*ntermin zawsze dominowałby nad innymi dla dowolnej wystarczająco dużej wartości n.

To właśnie oznacza notacja bitowa O: oznacza „jaka jest kolejność terminu dominującego dla każdego wystarczająco dużego n”.

Mogę dodać coś ciekawego, co czytałem w książce Kormena itp. Dawno temu. Teraz wyobraź sobie problem, w którym musimy znaleźć rozwiązanie w przestrzeni problemów. Ta przestrzeń problemowa powinna być skończona.

Teraz, jeśli możesz udowodnić, że przy każdej iteracji algorytmu odcinasz ułamek tej przestrzeni, czyli nie mniej niż pewien limit, oznacza to, że twój algorytm działa w czasie O (logN).

Powinienem zaznaczyć, że mówimy tutaj o granicy względnej, a nie absolutnej. Wyszukiwanie binarne jest klasycznym przykładem. Na każdym kroku wyrzucamy 1/2 problematycznej przestrzeni. Ale wyszukiwanie binarne to nie jedyny taki przykład. Załóżmy, że w jakiś sposób udowodniłeś, że na każdym kroku wyrzucasz co najmniej 1/128 problematycznej przestrzeni. Oznacza to, że twój program nadal działa w czasie O (logN), chociaż znacznie wolniej niż wyszukiwanie binarne. To bardzo dobra wskazówka w analizie algorytmów rekurencyjnych. Często można udowodnić, że na każdym etapie rekursja nie wykorzysta kilku wariantów, co prowadzi do odcięcia pewnej części w przestrzeni problemowej.

Mogę podać przykład dla pętli for, a może po zrozumieniu koncepcji może być łatwiejsze do zrozumienia w różnych kontekstach.

Oznacza to, że w pętli krok rośnie wykładniczo. Na przykład

for (i=1; i<=n; i=i*2) {;}

Złożoność notacji O tego programu to O (log (n)). Spróbujmy wykonać pętlę ręcznie (n jest gdzieś pomiędzy 512 a 1023 (z wyjątkiem 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Chociaż n jest gdzieś pomiędzy 512 a 1023, ma miejsce tylko 10 iteracji. Wynika to z faktu, że krok w pętli rośnie wykładniczo, a zatem osiągnięcie zaledwie 10 iteracji zajmuje 10 minut.

Logarytm x (do podstawy a) jest funkcją odwrotną do ^ x.

To tak, jakby powiedzieć, że logarytm jest odwrotnością wykładniczą.

Teraz spróbuj to zobaczyć w ten sposób, jeśli wykładniczy rośnie bardzo szybko, to logarytm rośnie (odwrotnie) bardzo wolno.

Różnica między O (n) i O (log (n)) jest ogromna, podobna do różnicy między O (n) i O (a ^ n) (a jest stałą).

W rzeczywistości, jeśli masz listę n elementów i utworzysz drzewo binarne z tej listy (jak w algorytmie dziel i zwycięż), będziesz dalej dzielić przez 2, aż dojdziesz do list rozmiaru 1 (liście).

W pierwszym kroku dzielisz przez 2. Masz wtedy 2 listy (2 ^ 1), dzielisz każdą przez 2, więc masz 4 listy (2 ^ 2), dzielisz ponownie, masz 8 list (2 ^ 3 ) i tak dalej, aż rozmiar listy wyniesie 1

To daje ci równanie:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(bierzesz lg z każdej strony, lg jest bazą logów 2)

Za każdym razem, gdy piszemy algorytm lub kod, staramy się analizować jego asymptotyczną złożoność. Różni się od swojej złożoności czasowej .

Złożoność asymptotyczna to zachowanie czasu wykonania algorytmu, zaś złożoność czasowa to rzeczywisty czas wykonania. Ale niektórzy używają tych terminów zamiennie.

Ponieważ złożoność czasu zależy od różnych parametrów mianowicie.
1. System fizyczny
2. Język programowania
3. Styl kodowania
4. I wiele więcej ......

Rzeczywisty czas wykonania nie jest dobrym miernikiem do analizy.

Zamiast tego bierzemy wielkość wejściową jako parametr, ponieważ niezależnie od kodu, dane wejściowe są takie same. Czas wykonania jest więc funkcją wielkości wejściowej.

Poniżej znajduje się przykład liniowego algorytmu czasu

Wyszukiwanie liniowe
Biorąc pod uwagę n elementów wejściowych, aby wyszukać element w tablicy, potrzebujesz co najwyżej 'n' porównań . Innymi słowy, bez względu na to, jakiego języka programowania używasz, jaki styl kodowania preferujesz, na jakim systemie go wykonujesz. W najgorszym przypadku wymaga tylko porównań n. Czas wykonania jest liniowo proporcjonalny do wielkości wejściowej.

I nie jest to tylko wyszukiwanie, cokolwiek może być pracą (przyrost, porównanie lub dowolna operacja), jest funkcją wielkości wejściowej.

Kiedy więc powiesz, że dowolny algorytm ma wartość O (log n), oznacza to, że czas wykonania to log razy razy wielkość wejściowa n.

Wraz ze wzrostem wielkości wejściowej zwiększa się wykonywana praca (tutaj czas wykonania). (Stąd proporcjonalność)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Zobacz, jak zwiększa się rozmiar wejściowy, zwiększona jest wykonywana praca i jest on niezależny od dowolnej maszyny. A jeśli spróbujesz dowiedzieć się, jaka jest wartość jednostek pracy, to tak naprawdę zależy to od powyższych parametrów. Zmieni się w zależności od systemu i wszystkich innych.

log x to base b = y jest odwrotnością b^y = x

Jeśli masz drzewo M-ary o głębokości d i rozmiarze n, to:

• przemierzając całe drzewo ~ O (M ^ d) = O (n)

• Spacerując pojedynczą ścieżką po drzewie ~ O (d) = O (log n do bazy M)

W technologii informatycznej oznacza to, że:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Wydaje się, że notacja ta pochodzi głównie z matematyki.

W tym artykule jest cytat: DE Knuth, „BIG OMICRON AND BIG OMEGA AND BIG THETA”, 1976 :

Na podstawie omawianych tutaj zagadnień proponuję, aby członkowie SIGACT oraz redaktorzy czasopism informatycznych i matematycznych przyjęli zapisy jak zdefiniowano powyżej, chyba że wkrótce można znaleźć lepszą alternatywę .

Dzisiaj jest 2016, ale używamy go do dziś.

W analizie matematycznej oznacza to, że:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Ale nawet w analizie matematycznej czasami ten symbol był używany w znaczeniu „C * g (n)> f (n)> 0”.

Jak wiem z uniwersytetu, symbol wprowadził niemiecki matematyk Landau (1877–1938)

Kompletnym przykładem binarnym jest O (ln n), ponieważ wyszukiwanie wygląda następująco:

1 2 3 4 5 6 7 8 9 10 11 12

Wyszukiwanie 4 daje 3 trafienia: 6, 3, a następnie 4. I log2 12 = 3, co jest dobrym przybliżeniem do liczby trafień w razie potrzeby.

Jeśli szukasz odpowiedzi opartej na intuicji, chciałbym przedstawić dwie interpretacje.

1. Wyobraź sobie również bardzo wysokie wzgórze z bardzo szeroką bazą. Aby dostać się na szczyt wzgórza, są dwa sposoby: jeden jest dedykowaną ścieżką, która biegnie spiralnie wokół wzgórza, docierając do szczytu, a drugi: mały taras jak rzeźby wycięte w celu zapewnienia schodów. Teraz, jeśli pierwszym sposobem jest osiągnięcie w czasie liniowym O (n), drugim jest O (log n).

2. Wyobraź sobie algorytm, który przyjmuje liczbę całkowitą njako dane wejściowe i kończy się w czasie proporcjonalnym do ntego czasu, to O (n) lub theta (n), ale jeśli działa w proporcji czasowej do tego, number of digits or the number of bits in the binary representation on numberwówczas algorytm działa w O (log n) lub theta (log n) czas.

Algorytmy paradygmatu Dziel i rządź mają złożoność O (logn). Jeden przykład tutaj, oblicz swoją własną funkcję mocy,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

z http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/