To wcześniejsze pytanie dotyczy niektórych czynników, które mogą powodować, że algorytm ma złożoność O (log n).
Co spowodowałoby, że algorytm miałby złożoność czasową O (log log n)?
To wcześniejsze pytanie dotyczy niektórych czynników, które mogą powodować, że algorytm ma złożoność O (log n).
Co spowodowałoby, że algorytm miałby złożoność czasową O (log log n)?
Odpowiedzi:
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.
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
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
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:
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).
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 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!
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):
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.