Algorithmen für die Big-O-Analyse

Question

Welche Algorithmen finden Sie erstaunlich (hart, seltsam) Komplexitätsanalyse in Bezug auf beide - Resultierende O Notation und Einzigartigkeit in der Art und Weise sie analysiert werden?

Answer 1

Ich habe (ziemlich) viele Beispiele:

• El gewerkschaft-finden Datenstruktur, die Operationen in (amortisierter) inverser Ackermann-Zeit unterstützt. Das ist besonders schön, weil die Datenstruktur unglaublich einfach zu codieren ist.
• Bäume spreizen die sich selbst ausgleichende Binärbäume sind (d. h. außer der BST werden keine weiteren Informationen gespeichert - keine Rot/Schwarz-Informationen). Amortisierte Analyse wurde im Wesentlichen erfunden, um Schranken für Spreizbäume zu beweisen; Spreizbäume laufen in abgeschrieben logarithmische Zeit, aber im schlimmsten Fall lineare Zeit. Die Beweise sind cool.
• Fibonacci-Haufen die die meisten Operationen in der Prioritätswarteschlange in amortisierter konstanter Zeit durchführen und so die Laufzeit von Dijkstra-Algorithmus und andere Probleme. Wie bei den Spreizbäumen gibt es auch hier raffinierte Beweise für "potenzielle Funktionen".
• Bernard Chazelle's Algorithmus zur Berechnung von minimalen Spannbäumen in linearer, inverser Ackermann-Zeit. Der Algorithmus verwendet weiche Böden , eine Variante des traditionellen Prioritäts-Warteschlange Es kann jedoch sein, dass eine gewisse "Korruption" auftritt und die Anfragen nicht korrekt beantwortet werden.
• Apropos MSTs: Ein optimaler Algorithmus wurde bereits gegeben von Pettie und Ramachandran , aber wir kennen die Laufzeit nicht!
• Viele randomisierte Algorithmen haben interessante Analysen. Ich werde nur ein Beispiel erwähnen: Die Delaunay-Triangulation kann in erwarteter O(n log n)-Zeit berechnet werden durch schrittweises Hinzufügen von Punkten Die Analyse ist anscheinend sehr kompliziert, obwohl ich sie nicht gesehen habe.
• Algorithmen, die "Bittricks" verwenden, können ganz nett sein, z. B. Sortierung in O(n log log n) Zeit (und linearen Raum) - das ist richtig, es durchbricht die O(n log n)-Schranke, indem es mehr als nur Vergleiche verwendet.
• Cache-oblivious Algorithmen haben oft interessante Analysen. Zum Beispiel, cache-oblivious Prioritäts-Warteschlangen (siehe Seite 3) verwenden log log n Stufen der Größe n, n 2/3 , n 4/9 , und so weiter.
• (Statische) Range-Minimum-Abfragen auf Arrays sind ordentlich. Die Standardnachweis testet Ihre Grenzen in Bezug auf die Reduktion: Range-Minimum-Abfragen werden auf den kleinsten gemeinsamen Vorfahren in Bäumen reduziert, der wiederum auf eine Range-Minimum-Abfrage in einem bestimmten Baum reduziert wird. freundlich von Arrays. Im letzten Schritt kommt ebenfalls ein netter Trick zum Einsatz.

Answer 2

Ackermannsche Funktion .

Answer 3

Das hier ist ziemlich simpel, aber Comb Sort hat mich ein bisschen umgehauen.

http://en.wikipedia.org/wiki/Comb_sort

Es ist ein so einfacher Algorithmus, dass er sich größtenteils wie eine übermäßig komplizierte Bubble-Sortierung liest, aber er ist O(n*Log[n]). Ich finde das einigermaßen beeindruckend.

Die Vielzahl der Algorithmen für schnelle Fourier-Transformationen ist ebenfalls beeindruckend, die Mathematik, die ihre Gültigkeit beweist, ist verblüffend, und es hat Spaß gemacht, einige davon selbst zu beweisen.

http://en.wikipedia.org/wiki/Fast_Fourier_transform

Ich kann die Algorithmen der Primzahl-Radix, der Mehrfach-Primzahl-Radix und der gemischten Radix relativ leicht verstehen, aber ein Algorithmus, der mit Mengen arbeitet, deren Größe Primzahlen sind, ist ziemlich cool.

Answer 4

Die Analyse der geordneten 2D-Suche ist recht interessant. Man hat eine 2-dimensionale numerische Anordnung von Zahlen NxN, wobei jede Zeile von links nach rechts und jede Spalte von oben nach unten sortiert ist. Die Aufgabe besteht darin, eine bestimmte Zahl in der Matrix zu finden.

Der rekursive Algorithmus: das Element in der Mitte auswählen, mit der Zielzahl vergleichen, ein Viertel des Feldes verwerfen (je nach Ergebnis des Vergleichs), rekursiv auf die verbleibenden 3 Viertel anwenden, ist recht interessant zu analysieren.

Answer 5

Ich stimme für die nicht-deterministische polynomiale Komplexität, insbesondere mit der (zugegebenermaßen als unwahrscheinlich angesehenen) Möglichkeit, dass sie sich als gleichwertig mit der polynomialen Komplexität erweisen könnte. Ebenso alles, was theoretisch von der Quanteninformatik profitieren kann (Anmerkung: Diese Gruppe umfasst keineswegs alle Algorithmen).

Ein weiterer Punkt, für den ich stimmen würde, sind allgemeine mathematische Operationen mit Zahlen beliebiger Genauigkeit - hier muss man berücksichtigen, dass das Multiplizieren großer Zahlen teurer ist als das Multiplizieren kleiner Zahlen. In Knuth wird dies ausführlich analysiert (was für niemanden eine Neuigkeit sein sollte). Karatsubas Methode ist recht ordentlich: Man halbiert die beiden Faktoren durch die Ziffern (A1;A2)(B1;B2) und multipliziert A1 B1, A1 B2, A2 B1, A2 B2 getrennt, und kombiniert dann die Ergebnisse. Rekursion, falls gewünscht...