Co spowodowałoby, że algorytm miałby złożoność O (log log n)?

Odpowiedzi:

218

Terminy O (log log n) mogą pojawiać się w wielu różnych miejscach, ale zazwyczaj istnieją dwie główne trasy, które docierają do tego środowiska wykonawczego.

Kurczy się o pierwiastek kwadratowy

Jak wspomniano w odpowiedzi na powiązane pytanie, częstym sposobem, w jaki algorytm ma złożoność czasową O (log n), jest działanie tego algorytmu poprzez wielokrotne zmniejszanie rozmiaru danych wejściowych o pewien stały współczynnik w każdej iteracji. W takim przypadku algorytm musi kończyć się po O (log n) iteracjach, ponieważ po zrobieniu O (log n) podziałów przez stałą algorytm musi zmniejszyć rozmiar problemu do 0 lub 1. Dlatego np. , wyszukiwanie binarne ma złożoność O (log n).

Co ciekawe, istnieje podobny sposób zmniejszania rozmiaru problemu, który daje czasy wykonywania w postaci O (log log n). Zamiast dzielić dane wejściowe na pół w każdej warstwie, co się stanie, jeśli weźmiemy pierwiastek kwadratowy z rozmiaru dla każdej warstwy?

Na przykład weźmy liczbę 65 536. Ile razy musimy to podzielić przez 2, aż zejdziemy do 1? Jeśli to zrobimy, otrzymamy

  • 65 536/2 = 32768
  • 32 768/2 = 16 384
  • 16 384/2 = 8 192
  • 8192/2 = 4096
  • 4096/2 = 2048
  • 2048/2 = 1024
  • 1024/2 = 512
  • 512/2 = 256
  • 256/2 = 128
  • 128/2 = 64
  • 64/2 = 32
  • 32/2 = 16
  • 16/2 = 8
  • 8/2 = 4
  • 4/2 = 2
  • 2/2 = 1

Ten proces składa się z 16 kroków i jest również przypadek, że 65 536 = 2 16 .

Ale jeśli weźmiemy pierwiastek kwadratowy na każdym poziomie, otrzymamy

  • √65,536 = 256
  • √256 = 16
  • √16 = 4
  • √4 = 2

Zauważ, że potrzeba tylko czterech kroków, aby zejść do 2. Dlaczego tak jest?

Najpierw intuicyjne wyjaśnienie. Ile cyfr składa się z liczb n i √n? Liczba n zawiera w przybliżeniu log n cyfr, a w przybliżeniu log (√n) = log (n 1/2 ) = (1/2) log n cyfr w √n. Oznacza to, że za każdym razem, gdy bierzesz pierwiastek kwadratowy, zmniejszasz mniej więcej o połowę liczbę cyfr w liczbie. Ponieważ możesz zmniejszyć o połowę ilość k O (log k) razy, zanim spadnie ona do stałej (powiedzmy 2), oznacza to, że możesz wziąć pierwiastek kwadratowy tylko O ​​(log log n) razy, zanim zmniejszysz liczbę do jakiejś stałej (powiedzmy 2).

Teraz zróbmy trochę matematyki, aby było to rygorystyczne. Le'ts przepisują powyższą sekwencję w kategoriach potęgi dwóch:

  • √65,536 = √2 16 = (2 16 ) 1/2 = 2 8 = 256
  • √256 = √2 8 = (2 8 ) 1/2 = 2 4 = 16
  • √16 = √2 4 = (2 4 ) 1/2 = 2 2 = 4
  • √4 = √2 2 = (2 2 ) 1/2 = 2 1 = 2

Zauważ, że postępowaliśmy zgodnie z sekwencją 2 16 → 2 8 → 2 4 → 2 2 → 2 1 . W każdej iteracji przecinamy wykładnik potęgi dwóch na pół. To ciekawe, ponieważ łączy się to z tym, co już wiemy - liczbę k można podzielić tylko na pół O (log k) razy, zanim spadnie do zera.

Więc weź dowolną liczbę n i zapisz ją jako n = 2 k . Za każdym razem, gdy bierzesz pierwiastek kwadratowy z n, dzielisz o połowę wykładnik w tym równaniu. Dlatego można zastosować tylko pierwiastki kwadratowe O (log k), zanim k spadnie do 1 lub mniej (w którym to przypadku n spadnie do 2 lub mniej). Ponieważ n = 2 k , oznacza to, że k = log 2 n, a zatem liczba branych pierwiastków kwadratowych wynosi O (log k) = O (log log n). Dlatego jeśli istnieje algorytm, który działa poprzez wielokrotne redukowanie problemu do podproblemu o rozmiarze, który jest pierwiastkiem kwadratowym z pierwotnego rozmiaru problemu, algorytm ten zakończy się po O (log log n) krokach.

Jednym z rzeczywistych przykładów jest drzewo van Emde Boas(vEB-tree) struktura danych. Drzewo vEB to wyspecjalizowana struktura danych do przechowywania liczb całkowitych z zakresu 0 ... N - 1. Działa w następujący sposób: węzeł główny drzewa zawiera wskaźniki √N, dzieląc zakres 0 ... N - 1 na √N koszy, z których każdy zawiera zakres z grubsza √N liczb całkowitych. Te koszyki są następnie wewnętrznie podzielone na koszyki √ (√ N), z których każdy zawiera mniej więcej √ (√ N) elementów. Aby przejść przez drzewo, zaczynasz od korzenia, określasz, do którego zasobnika należysz, a następnie rekurencyjnie kontynuujesz w odpowiednim poddrzewie. Ze względu na strukturę drzewa vEB, możesz określić w czasie O (1), w które poddrzewo zejdzie, a więc po krokach O (log log N) dotrzesz do dołu drzewa. W związku z tym wyszukiwanie w drzewie vEB zajmuje tylko czas O (log log N).

Innym przykładem jest algorytm najbliższej pary punktów Hopcroft-Fortune . Ten algorytm próbuje znaleźć dwa najbliższe punkty w zbiorze punktów 2D. Działa poprzez tworzenie siatki koszyków i rozdzielanie punktów do tych koszy. Jeśli w jakimkolwiek punkcie algorytmu zostanie znaleziony zasobnik zawierający więcej niż √N punktów, algorytm rekurencyjnie przetwarza ten zasobnik. Maksymalna głębokość rekursji wynosi zatem O (log log n), a na podstawie analizy drzewa rekurencji można wykazać, że każda warstwa w drzewie działa O (n). Dlatego całkowity czas działania algorytmu wynosi O (n log log n).

O (log n) Algorytmy dla małych wejść

Istnieją inne algorytmy, które osiągają O (log log n) środowiska uruchomieniowego przy użyciu algorytmów, takich jak wyszukiwanie binarne na obiektach o rozmiarze O (log n). Na przykład struktura danych x-fast trie przeprowadza wyszukiwanie binarne na warstwach drzewa o wysokości O (log U), więc czas wykonywania niektórych jej operacji wynosi O (log log U). Powiązane tryby y-fast uzyskują niektóre ze swoich środowisk wykonawczych O (log log U), utrzymując zbalansowane BST węzłów O (log U) każdy, umożliwiając wyszukiwanie w tych drzewach w czasie O (log log U). Drzewo tango i pokrewne drzewo multisplay struktury danych skończyć z O (log log n) terminu w swoich analizach, ponieważ utrzymują one drzew, które zawierają O (log n) pozycje każdego.

Inne przykłady

Inne algorytmy osiągają czas wykonania O (log log n) w inny sposób. Wyszukiwanie interpolacyjne oczekiwało w czasie wykonywania O (log log n) znalezienia liczby w posortowanej tablicy, ale analiza jest dość skomplikowana. Ostatecznie prace analityczne poprzez wykazanie, że liczba iteracji jest równa liczbie k takie, że n 2 -k ≤ 2, dla której log log n jest poprawne rozwiązanie. Niektóre algorytmy, takie jak algorytm Cheriton-Tarjan MST , dochodzą do środowiska wykonawczego obejmującego O (log log n), rozwiązując złożony problem optymalizacji z ograniczeniami.

Mam nadzieję że to pomoże!

templatetypedef
źródło
5
@ JonathonReinhart - tak się złożyło, że to było coś, co uważałem za (a) naprawdę fajne i (b) mało znane. Zawsze chętnie udostępniam takie rzeczy! :-)
templatetypedef
1
@ Mahesha999 Stack Overflow aktywnie zachęca użytkowników do odpowiadania na ich własne pytania . :-)
templatetypedef
zgadując, jakie inne konsekwencje może mieć „Odpowiedz na swoje własne pytanie” na dole strony Zadaj pytanie lub po prostu włącza pole tekstowe odpowiedzi na stronie pytania.
Mahesha999
1
Ważna linia: Dlatego, jeśli istnieje algorytm, który działa poprzez wielokrotne redukowanie problemu do podproblemu o rozmiarze, który jest pierwiastkiem kwadratowym z pierwotnego rozmiaru problemu, algorytm ten zakończy działanie po O (log log n) krokach.
Gun2sh
3

Jednym ze sposobów, aby zobaczyć współczynnik O (log log n) w złożoności czasowej, jest podział podobny do rzeczy wyjaśnionych w drugiej odpowiedzi, ale jest inny sposób, aby zobaczyć ten czynnik, gdy chcemy dokonać wymiany między czasem a przestrzenią / czasem oraz aproksymacja / czas i twardość / ... algorytmów i mamy sztuczną iterację naszego algorytmu.

Na przykład SSSP (Single source shortest path) ma algorytm O (n) na grafach planarnych, ale przed tym skomplikowanym algorytmem istniał znacznie łatwiejszy algorytm (ale nadal raczej trudny) z czasem działania O (n log log n), Podstawa algorytmu jest następująca (tylko bardzo przybliżony opis, proponuję pominąć zrozumienie tej części i przeczytać drugą część odpowiedzi):

  1. podziel wykres na części o rozmiarze O (log n / (log log n)) z pewnymi ograniczeniami.
  2. Załóżmy, że każda z wymienionych części jest węzłem w nowym grafie G ', a następnie oblicz SSSP dla G' w czasie O (| G '| * log | G' |) ==> tutaj, ponieważ | G '| = O (| G | * log log n / log n) możemy zobaczyć współczynnik (log log n).
  3. Oblicz SSSP dla każdej części: ponownie, ponieważ mamy część O (| G '|) i możemy obliczyć SSSP dla wszystkich części w czasie | n / logn | * | log n / log logn * log (logn / log log n).
  4. zaktualizuj wagi, tę część można wykonać w O (n). aby uzyskać więcej informacji, te notatki z wykładów są dobre.

Chodzi mi jednak o to, że tutaj wybieramy podział na rozmiar O (log n / (log log n)). Jeśli wybierzemy inne podziały, takie jak O (log n / (log log n) ^ 2), który może działać szybciej i przyniesie inny wynik. Chodzi mi o to, że w wielu przypadkach (jak w algorytmach aproksymacyjnych lub algorytmach losowych, czy algorytmach takich jak SSSP jak wyżej), kiedy iterujemy coś (podproblemy, możliwe rozwiązania, ...), wybieramy liczbę iteracji odpowiadającą temu mamy (czas / przestrzeń / złożoność algorytmu / stały współczynnik algorytmu, ...). Może więc widzimy bardziej skomplikowane rzeczy niż "log log n" w prawdziwych algorytmach pracy.

Saeed Amiri
źródło