Algorithmen für große O-Analyse

Ich habe (durchaus) ein paar Beispiele:

• Die union-find Datenstruktur, die Operationen in (amortisierter) inverser Ackermann-Zeit unterstützt. Es ist besonders schön, weil die Datenstruktur unglaublich einfach zu programmieren ist.
• Splay-Bäume , bei denen es sich um selbstbalancierende Binärbäume handelt (das heißt, außer der BST-Nr. werden keine zusätzlichen Informationen gespeichert) rot / schwarz Informationen Amortisierte Analyse wurde im Wesentlichen erfunden, um Grenzen für Splay-Bäume zu beweisen, Splay-Bäume laufen in amortized logarithmische Zeit, aber lineare Zeit im schlimmsten Fall. Die Beweise sind cool.
• Fibonacci-Heaps , die die meisten Warteschlangenoperationen in der amortisierten konstanten Zeit durchführen und somit die Laufzeit von Dijkstra's Algorithmus und andere Probleme. Wie bei Splay Trees gibt es glatte "potentielle Funktion" Beweise.
• Bernard Chazelles Algorithmus zur Berechnung minimaler Spannbäume in linearen Zeiten inverser Ackermann-Zeit. Der Algorithmus verwendet weiche Haufen , eine Variante des traditionellen priority queue , mit der Ausnahme, dass" Korruption "auftreten kann und Abfragen möglicherweise nicht korrekt beantwortet werden.
• Zum Thema MST: Ein optimaler Algorithmus wurde von Pettie und Ramachandran gegeben / a>, aber wir kennen die Laufzeit nicht!
• Viele randomisierte Algorithmen haben interessierte Analysen. Ich erwähne nur ein Beispiel: Die Delaunay-Triangulation kann in der erwarteten O (n log n) -Zeit durch inkrementelle Addition von Punkten ; die Analyse ist anscheinend kompliziert, obwohl ich sie nicht gesehen habe.
• Algorithmen, die "Bittricks" verwenden, können ordentlich sein, z. Sortierung in O (n log log n) Zeit (und linearer Raum) - das stimmt , es bricht die O (n log n) Schranke, indem es mehr als nur Vergleiche verwendet.
• Cache-Vergessen-Algorithmen haben oft interessante Analysen. Zum Beispiel verwenden speicherunabhängige Prioritätswarteschlangen (siehe Seite 3) Protokollebenen der Größen n, n 2/3, n 4/9 und so weiter
• (Statische) Range-Minimum-Abfragen für Arrays sind ordentlich. Der Standardproof testet Ihre Grenzen in Bezug auf die Reduzierung: Bereich-Minimum-Abfragen wird auf den kleinsten gemeinsamen Vorfahren in Bäumen reduziert, der wiederum auf einen Bereich reduziert wird - minimale Abfragen in einer bestimmten Art von Arrays. Der letzte Schritt verwendet auch einen süßen Trick.

Das hier ist ziemlich einfach, aber Comb Sort macht mir ein bisschen weh.

Ссылка

Es ist so ein einfacher Algorithmus, der sich größtenteils wie eine übermäßig komplizierte Blasensortierung liest, aber es ist O (n * Log [n]). Ich finde das leicht beeindruckend.

Die Fülle von Algorithmen für schnelle Fourier-Transformationen ist auch beeindruckend, die Mathematik, die ihre Gültigkeit beweist, ist trippy und es hat Spaß gemacht, einige allein zu beweisen.

Ссылка

Ich kann ziemlich einfach die Primzahl-Radix-, Mehrfach-Primzahl-Radix- und Mixed-Radix-Algorithmen verstehen, aber eine, die an Sets arbeitet, deren Größe prim ist, ist ziemlich cool.

Nicht-deterministisch polynomiale Komplexität erhält meine Stimme, insbesondere mit der (zugegebenermaßen als unwahrscheinlich angesehenen) Möglichkeit, dass sie sich als Polynom herausstellen kann. In der gleichen Weise, alles, was theoretisch von Quanten-Computing profitieren kann (N.B. dieses Set ist keineswegs alle Algorithmen).

Der andere, der meine Stimme erhalten würde, wäre eine gewöhnliche mathematische Operation mit Zahlen mit beliebiger Genauigkeit - hier müssen Sie berücksichtigen, dass die Multiplikation großer Zahlen teurer ist als die Multiplikation kleinerer Zahlen. Es gibt eine Menge Analyse in Knuth (was für niemanden neu sein sollte). Karatsubas Methode ist ziemlich ordentlich: Schneiden Sie die zwei Faktoren durch die Ziffer (A1; A2) (B1; B2) und multiplizieren Sie A1 B1, A1 B2, A2 B1, A2 B2 und kombinieren Sie dann die Ergebnisse. Rekursiv, wenn gewünscht ...

Shell sortieren. Es gibt Unmengen an Varianten mit verschiedenen Inkrementen, von denen die meisten keinen Nutzen haben, außer dass sie Komplexitätsanalyse einfacher .