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

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)?

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.

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.

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.

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.

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).