Amarengo

Articles and news

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

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!

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.