Godne uwagi przykłady idei pierwiastka kwadratowego w analizie złożoności

Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = $\max \left\{k, n/k\right\}$$k=\sqrt n$

• algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w $O(\sqrt n)$ ,
• statyczne zliczanie zakresu ortogonalnego 2D w czasie $O(\sqrt n)$ i pamięci $O(n)$ ,
• kolejka priorytetowa z EXTRACT-MIN w $O(\sqrt[k] n)$ i DECREASE-KEY w $O(1)$ ,
• kolorowanie trójkolorowego wykresu kolorami $O(\sqrt n)$ w czasie wielomianowym,

żeby wymienić tylko kilka.

Chociaż takie algorytmy często nie są optymalne, są łatwe do zrozumienia dla studentów i dobrze pokazują, że naiwne granice nie są optymalne. Ponadto struktury danych oparte na pierwiastkach kwadratowych są czasami bardziej praktyczne niż ich odpowiedniki oparte na drzewie binarnym ze względu na łatwość obsługi pamięci podręcznej (nie biorąc pod uwagę technik nieobsługujących pamięci podręcznej). Dlatego przykładam dużą wagę do tego tematu podczas nauczania.

Interesują mnie bardziej charakterystyczne przykłady tego rodzaju. Szukam więc (najlepiej eleganckich) algorytmów, struktur danych, protokołów komunikacyjnych itp., Których analiza opiera się na idei pierwiastka kwadratowego. Ich asymptotyki nie muszą być optymalne.

Artykuł Chazelle, Liu i Magena Sublinear Geometric Al Algorytmy (STOC 2003, SICOMP 2006) ma kilka sprytnych zastosowań następującej sztuczki losowego próbkowania. Odmiany tej samej sztuczki były wcześniej używane przez Gärtnera i Welzla [ DCG 2001 ], którzy cytują pierwsze wydanie CLR (1990).

Załóżmy, że otrzymaliśmy posortowaną okrągłą listę liczb przechowywaną w ciągłym bloku pamięci. Oznacza to, że mamy dwie tablice i , gdzieN e x t [ 1 .. n $Key[1..n]$$Next[1..n]$

• $Key[1..n]$ przechowuje zestaw liczb w dowolnej kolejności;$n$
• Jeśli jest największą liczbą w zestawie, to jest najmniejszą liczbą w zestawie; w przeciwnym razie to najmniejsza liczba w zestawie, która jest większa niż .$Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Następnie możemy znaleźć następcę podanej liczby w oczekiwanym czasie w następujący sposób:$x$$O(\sqrt{n})$

• Wybierz losową próbkę elementów tablicy . Niech będzie największą próbką, która jest mniejsza niż (lub największą próbką, jeśli wszystkie próbki są większe niż ).$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Postępuj zgodnie z wskaźnikami z aż zobaczymy liczbę większą lub równą (po zawinięciu, jeśli wszystkie próbki były większe niż ).$Next$$Key[j]$$x$$x$

Stosunkowo proste zastosowanie lematu Yao sugeruje, że oczekiwany czas jest optymalny. Każdy deterministyczny algorytm dla tego problemu wymaga czasu w najgorszym przypadku.$O(\sqrt{n})$$\Omega(n)$

$O(m^{3/2})$$m$$O(m^{3/2})$$n-k$$k$$n-k$$k$$m/k+k$$O(\sqrt m)$$O(m^{3/2})$