o(log log N) terminy mogą pojawiać się w różnych miejscach, ale zazwyczaj istnieją dwie główne trasy, które dotrą do tego środowiska.
kurczenie się o pierwiastek kwadratowy
jak wspomniano w odpowiedzi na połączone pytanie, powszechnym sposobem na to, aby algorytm miał złożoność czasową O(log N), jest działanie tego algorytmu poprzez wielokrotne zmniejszanie rozmiaru danych wejściowych o pewien stały czynnik w każdej iteracji. W takim przypadku algorytm musi zakończyć się po iteracjach O (log N), ponieważ po wykonaniu podziałów o(log n) 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 wykonania formularza O (log log N). Zamiast dzielić dane wejściowe na pół w każdej warstwie, co się stanie, jeśli weźmiemy pierwiastek kwadratowy wielkości w każdej warstwie?
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 = 32,768
- 32,768 / 2 = 16,384
- 16,384 / 2 = 8,192
- 8,192 / 2 = 4,096
- 4,096 / 2 = 2,048
- 2,048 / 2 = 1,024
- 1,024 / 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 trwa 16 kroków, i jest to również przypadek, że 65,536 = 216.
ale jeśli weźmiemy pierwiastek kwadratowy na każdym poziomie, otrzymamy
- √65,536 = 256
- √256 = 16
- √16 = 4
- √4 = 2
zauważ, że to tylko cztery kroki, aby dostać się aż do 2. Dlaczego?
po pierwsze, intuicyjne Wyjaśnienie. Ile cyfr jest w cyfrach n i √n? W liczbie n znajduje się w przybliżeniu log n cyfr, a w przybliżeniu log (√n) = log (N1/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 tej liczbie. Ponieważ możesz zmniejszyć tylko o połowę ilość k O (log K) razy, zanim spadnie do stałej(powiedzmy, 2), oznacza to, że możesz wziąć pierwiastki kwadratowe O (log log N) razy, zanim zmniejszysz liczbę do jakiejś stałej (powiedzmy, 2).
teraz, zróbmy trochę matematyki, aby to było rygorystyczne. Le ’ TS przepisuje powyższy ciąg pod względem potęg dwóch:
- √65,536 = √216 = (216)1/2 = 28 = 256
- √256 = √28 = (28)1/2 = 24 = 16
- √16 = √24 = (24)1/2 = 22 = 4
- √4 = √22 = (22)1/2 = 21 = 2
zauważ, że postępowaliśmy zgodnie z kolejnością 216 → 28 → 24 → 22 → 21. W każdej iteracji tniemy wykładnik potęgi dwóch na pół. To ciekawe, ponieważ łączy się to z tym, co już wiemy – możesz podzielić liczbę k na połowę o (log k) razy, zanim spadnie do zera.
więc weź dowolną liczbę n i zapisz ją jako n = 2K. Za każdym razem, gdy bierzesz pierwiastek z n, zmniejszasz o połowę wykładnik w tym równaniu. W związku z tym, może być tylko o (log k) pierwiastki kwadratowe stosowane przed k spada do 1 lub mniej (w tym przypadku N spada do 2 lub mniej). Ponieważ n = 2K, oznacza to, że K = log2 n, a zatem liczba pierwiastków kwadratowych wziętych wynosi O (log K) = O(log log N). Dlatego, jeśli istnieje algorytm, który działa poprzez wielokrotne zmniejszanie problemu do podproblemu o rozmiarze, który jest pierwiastkiem kwadratowym pierwotnego rozmiaru problemu, algorytm ten zakończy się po krokach O (log log N).
jednym z rzeczywistych przykładów jest struktura danych van Emde boas tree (vEB-tree). VEB-tree jest wyspecjalizowaną strukturą danych do przechowywania liczb całkowitych z zakresu 0 … N-1. To działa w następujący sposób: węzeł korzeniowy drzewa ma √n Wskaźniki w nim, dzieląc zakres 0 … N-1 w wiadrach √N, z których każde posiada zakres mniej więcej √n liczb całkowitych. Te wiadra są następnie wewnętrznie podzielone na √ (√n)wiadra, z których każdy zawiera mniej więcej √(√ n) elementy. Aby przejść przez drzewo, zaczynasz od korzenia, określasz, do którego wiadra należysz, a następnie rekurencyjnie kontynuujesz w odpowiednim poddrzewie. Ze względu na strukturę vEB-tree, możesz określić w czasie O(1), do którego podzbioru należy zejść, a więc po krokach o(log log N) dotrzesz do dna drzewa. W związku z tym, wyszukiwanie w drzewie vEB zajmuje tylko czas O(log log N).
Innym przykładem jest algorytm pary punktów Hopcroft-Fortune. Algorytm ten próbuje znaleźć dwa najbliższe punkty w zbiorze punktów 2D. Działa poprzez tworzenie siatki wiader i dystrybucję punktów do tych wiader. Jeśli w dowolnym punkcie algorytmu zostanie znalezione wiadro, które ma więcej niż √n punktów, algorytm rekurencyjnie przetwarza to wiadro. Maksymalna głębokość rekurencji wynosi zatem O(log log N), A korzystając z 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).
algorytmy O(log N) na małych wejściach
istnieje kilka innych algorytmów, które osiągają czasy uruchomienia O(log log n) za pomocą algorytmów takich jak wyszukiwanie binarne na obiektach O wielkości O(log N). Na przykład struktura danych X-fast trie wykonuje wyszukiwanie binarne po warstwach drzewa o wysokości O (log u), więc runtime dla niektórych jego operacji to O(log log U). Powiązane z nim y-fast trie pobiera część czasu pracy O(log log U), utrzymując zrównoważone 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 powiązane struktury danych drzewa multisplay kończą się terminem O(log log N) w swoich analizach, ponieważ utrzymują drzewa, które zawierają elementy O (log N) każdy.
inne przykłady
inne algorytmy osiągają runtime O(log log N) w inny sposób. Interpolacja wyszukiwanie oczekiwało runtime O (log log N) znaleźć liczbę w posortowanej tablicy, ale analiza jest dość zaangażowany. Ostatecznie analiza działa poprzez wykazanie, że liczba iteracji jest równa liczbie k, tak że n2-K ≤ 2, dla której log log N jest właściwym rozwiązaniem. Niektóre algorytmy, takie jak algorytm Cheriton-Tarjan MST, osiągają runtime z udziałem O(log log N), rozwiązując złożony problem związany z optymalizacją.
mam nadzieję, że to pomoże!