Bemerkenswerte Beispiele für die Quadratwurzel-Idee in der Komplexitätsanalyse

k = $\max \left\{k, n/k\right\}$$k=\sqrt n$

• Baby-Step-Riesenschritt-Algorithmus zur Berechnung des diskreten Logarithmus in ,$O(\sqrt n)$
• statische orthogonale 2D-Bereichszählung in -Zeit und -Speicher,O(n$O(\sqrt n)$$O(n)$
• Prioritätswarteschlange mit EXTRACT-MIN in und DECREASE-KEY in ,O(1$O(\sqrt[k] n)$$O(1)$
• Färben eines 3-farbigen Graphen mit Farben in Polynomzeit,$O(\sqrt n)$

nur um ein paar zu nennen.

Obwohl solche Algorithmen oft nicht optimal sind, sind sie für die Schüler leicht zu verstehen und zeigen schnell, dass naive Grenzen nicht optimal sind. Auch sind Quadratwurzel-Ideendatenstrukturen aufgrund der Cache-Freundlichkeit (ohne Berücksichtigung von Cache-vergessenden Techniken) manchmal praktischer als ihre Gegenstücke auf der Basis von Binärbäumen. Deshalb widme ich diesem Thema während des Unterrichts ein gutes Stück Aufmerksamkeit.

Ich interessiere mich für weitere Beispiele dieser Art. Daher suche ich nach (vorzugsweise eleganten) Algorithmen, Datenstrukturen, Kommunikationsprotokollen usw., deren Analyse auf der Quadratwurzel-Idee beruht. Ihre Asymptotik muss nicht optimal sein.

Chazelle, Liu und Magens Arbeit Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006) hat mehrere clevere Anwendungen des folgenden Stichprobentricks. Variationen desselben Tricks wurden zuvor von Gärtner und Welzl [ DCG 2001 ] verwendet, die die erste Ausgabe von CLR (1990) zitierten.

Angenommen, wir erhalten eine sortierte, zirkulär verknüpfte Liste von Zahlen, die in einem zusammenhängenden Speicherblock gespeichert sind. Das heißt, wir haben zwei Arrays und , wobeiN e x t [ 1 .. n $Key[1..n]$$Next[1..n]$

• $Key[1..n]$ speichert eine Menge von Zahlen in willkürlicher Reihenfolge.$n$
• Wenn die größte Zahl im Satz ist, ist die kleinste Zahl im Satz. Andernfalls ist die kleinste Zahl in der Gruppe, die größer als .K e y [ N e x t [ i ] ] K e y [ N e x t [ i ] ] K e y [ i $Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Dann können wir den Nachfolger einer gegebenen Zahl in erwarteter Zeit wie folgt finden:O ( $x$$O(\sqrt{n})$

• Wählen Sie eine zufällige Stichprobe von Elementen des Array- . Es sei das größte Sample, das kleiner als (oder das größte Sample, wenn alle Samples größer als ). KeyKey[j]x$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Folgen Sie den Zeigern von bis eine Zahl größer oder gleich angezeigt wird (nach dem Umbrechen, wenn alle Samples größer als ).K e y [ j ] x $Next$$Key[j]$$x$$x$

Eine relativ einfache Anwendung von Yaos Lemma impliziert, dass die erwartete optimal ist. Jeder deterministische Algorithmus für dieses Problem benötigt im schlimmsten Fall -Zeit.Ω(n$O(\sqrt{n})$$\Omega(n)$

Es gibt Dreiecke in jedem Eck-Graphen und diese können in werden. Es gibt viele Möglichkeiten, dies zu tun, aber ich denke, eine der frühesten ist Itai und Rodeh (STOC 1977) , die einen Algorithmus bereitstellen, der eine Folge von Iterationen in linearer Zeit durchläuft, von denen jede einen übergreifenden Wald aus dem Diagramm entfernt. In den frühen Iterationen, in denen die verbleibende mindestens Komponenten enthält, entfernt der Algorithmus mindestens Kanten pro Schritt, und in den späten Iterationen, in denen höchstens Komponenten enthalten sind, ist der maximale Grad und schrumpft jeweils um mindestens eine Schritt. Die Gesamtzahl der Iterationen beträgt also höchstensm O ( m 3 / 2 ) n - k k n - k k m / k + k O ( $O(m^{3/2})$$m$$O(m^{3/2})$$n-k$$k$$n-k$$k$$m/k+k$ und Auswahl des richtigen Kompromisses ergeben die Gesamtgrenze von für Iterationen und für die Zeit.O(m 3 / 2$O(\sqrt m)$$O(m^{3/2})$