Określanie, czy algorytm ma wartość O (log n)

25

Odświeżam moją teorię CS i chcę wiedzieć, jak rozpoznać złożoność algorytmu O (log n). W szczególności, czy istnieje łatwy sposób na identyfikację?

Wiem, że z O (n) zwykle masz pojedynczą pętlę; O (n ^ 2) jest podwójną pętlą; O (n ^ 3) jest potrójną pętlą itp. Co powiesz na O (log n)?

algorithms complexity big-o Atif
źródło
2
stackoverflow.com/questions/749819/... lub ten naprawdę długi
tekst
Ach, to jedyne miejsce, w którym nie wyglądałem :)
Atif

Odpowiedzi:

32

Wiem, że z O (n) zwykle masz pojedynczą pętlę; O (n ^ 2) jest podwójną pętlą; O (n ^ 3) jest potrójną pętlą itp. Co powiesz na O (log n)?

Naprawdę źle sobie z tym radzisz. Próbujesz zapamiętać, które wyrażenie big-O pasuje do danej struktury algorytmu, ale naprawdę powinieneś po prostu policzyć liczbę operacji wymaganych przez algorytm i porównać to z rozmiarem danych wejściowych. Algorytm, który zapętla się na całym wejściu, ma wydajność O (n), ponieważ uruchamia pętlę n razy, a nie dlatego, że ma pojedynczą pętlę. Oto pojedyncza pętla z wydajnością O (log n):

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Tak więc dowolnym algorytmem, w którym liczba wymaganych operacji jest rzędu logarytmu wielkości danych wejściowych, jest O (log n). Ważną rzeczą, którą mówi analiza Big-O, jest to, jak zmienia się czas wykonania algorytmu w stosunku do wielkości danych wejściowych: jeśli podwoisz wielkość danych wejściowych, czy algorytm wykona jeszcze 1 krok (O (log n)) , dwa razy więcej kroków (O (n)), cztery razy więcej kroków (O (n ^ 2)) itp.

Czy pomaga z doświadczenia wiedzieć, że algorytmy, które wielokrotnie dzielą dane wejściowe, zwykle mają „log n” jako składnik ich wydajności? Pewnie. Ale nie szukaj partycjonowania i przejdź do wniosku, że wydajność algorytmu to O (log n) - może to być coś w rodzaju O (n log n), co jest zupełnie inne.

Caleb
źródło
3
Zauważ, że bardziej potocznym sposobem na powiedzenie „w kolejności logarytmu wielkości” jest powiedzenie „w kolejności liczby cyfr w rozmiarze”.
@Caleb faktyczna podstawa logarytmu nie ma znaczenia przy mówieniu o skalowaniu.
@ Absolutne gadanie w Calleb nie ma sensu z big-O. Sformułowanie, które może ci się spodobać lepiej: gdy liczba cyfr się podwoi, liczba kroków się podwoi.
@ Absolutne gadanie w Calleb nie ma sensu z big-O. Sformułowanie, które może ci się spodobać lepiej: gdy liczba cyfr się podwoi, liczba kroków się podwoi.
@ ThorbjørnRavnAndersen Tak, to właśnie oznacza „logarytm wielkości”. Nie jestem pewien, na czym polega twój problem z tą frazą, z wyjątkiem tego, że wybrałbyś inaczej. Zasadniczo myślę, że się zgadzamy.
Caleb
25

Chodzi o to, że algorytm polega na tym, O(log n)że zamiast przewijać strukturę 1 na 1, dzielisz strukturę na pół w kółko i wykonujesz stałą liczbę operacji dla każdego podziału. Algorytmy wyszukiwania, w których przestrzeń odpowiedzi ciągle się dzieli O(log n). Przykładem tego jest wyszukiwanie binarne , w którym ciągle dzielisz uporządkowaną tablicę na pół w kółko, aż znajdziesz liczbę.

Uwaga: niekoniecznie musisz dzielić na równe części.

Casey Patton
źródło
1
Co jeśli podzielę dane wejściowe na dwie części, a następnie powtórzę 2 ^ (n / 2) razy na pozostałej części przed ponownym podzieleniem? (Oczywiście, co wiem, chciałem tylko pokazać przykład, w którym to uproszczone podejście zawodzi).
Tamás Szelei
@afish To dość rzadkie. Jest to niezwykle rzadkie podczas wyszukiwania.
Donal Fellows
1
@DonalFellows Algorytm algorytmiczny nie jest nauką empiryczną. I nie chodziło o wyszukiwanie, tylko o wzmiankę o log nwywołanych odruchach wyszukiwania binarnego u ludzi.
Tamás Szelei
2
Partycjonowanie nie powoduje, że algorytm O (log n) dodaje (zwykle) współczynnik log n do limitu big-O. Typy rekurencyjne, takie jak heapsort i scalesort, są idealnymi przykładami: dzielą dane wejściowe, ale następnie rekurencyjnie dzielą obie wynikowe partycje. Wynikiem jest wydajność O (n log n).
Caleb
@afish: Dobra uwaga. Moim celem z tą odpowiedzią jest, aby była jak najprostsza, biorąc pod uwagę charakter pytania. Zmieniłem linię „dzielisz konstrukcję na pół ...” na „dzielisz konstrukcję na pół ... i wykonujesz stałą liczbę operacji dla każdego podziału”, aby po prostu uzyskać ten punkt.
Casey Patton
2

Typowe przykłady dotyczą wyszukiwania binarnego. Na przykład algorytm wyszukiwania binarnego jest zwykle O(log n).

Jeśli masz drzewo wyszukiwania binarnego , wyszukiwanie, wstawianie i usuwanie są O(log n)skomplikowane.

Każda sytuacja, w której stale partycjonujesz przestrzeń, często wiąże się ze log nskładnikiem. To dlatego wiele algorytmów sortowania ma O(nlog n)złożoność, ponieważ często dzielą zestaw i sortują w miarę upływu czasu.

Kris Harper
źródło
1

Jeśli chcesz to tak proste jak „pojedyncza pętla -> O (n), podwójna pętla -> O (n ^ 2)”, odpowiedzią jest prawdopodobnie „Drzewo -> O (log n)”. Dokładniej przemierzając drzewo od korzenia do jednego (nie wszystkich!) Liścia lub na odwrót. Są to jednak wszystkie uproszczenia.

szalik
źródło
Co jest nie tak z moją odpowiedzią? Jestem otwarty na konstruktywną krytykę.
szalik
0

Chcesz wiedzieć, czy istnieje prosty sposób na określenie, czy algorytm to O (log N).

Cóż: po prostu biegnij i zmierz czas. Uruchom go dla danych wejściowych 1.000, 10.000, 100.000 i miliona.

Jeśli widzisz czas działania wynoszący 3,4,5,6 sekundy (lub kilka wielokrotności), możesz spokojnie powiedzieć, że jest to O (log N). Jeśli jest to bardziej: 1,10 100,1000 sekund, to prawdopodobnie jest to O (N). A jeśli jest to jak 3 40 500 600 000 sekund, to jest to O (N log N).

Pieter B.
źródło
Każdy powinien dać tę odpowiedź jeden głos pozytywny i jeden głos negatywny, oba z oczywistych powodów :-)
gnasher729