Andere Arten der Laufzeitanalyse als Worst-Case, Average-Case usw.?

Hier einige Möglichkeiten, um die Laufzeit eines Algorithmus zu analysieren:

1) Worst-Case-Analyse: Laufzeit auf der schlechtesten Instanz.

2) Durchschnittsfallanalyse: Erwartete Laufzeit einer zufälligen Instanz.

3) Amortisierte Analyse: Durchschnittliche Laufzeit in der schlechtesten Folge von Instanzen.

4) Geglättete Analyse: Erwartete Laufzeit für die schlimmste zufällig gestörte Instanz.

5) Analyse allgemeiner Fälle: Laufzeit auf der schlechtesten aller Instanzen mit Ausnahme einer kleinen Teilmenge.

Meine Frage: Ist das eine vollständige Liste?

Die Instanzoptimalität ist eine sehr interessante Eigenschaft von Algorithmen. Man kann Vorstellungen von Instanzenoptimalität verallgemeinern und überraschend interessante Vorstellungen entwickeln, die Worst-Case- und Average-Case-Analysen umfassen.

Obwohl es nicht ausschließlich in den Bereich der traditionellen Algorithmusanalyse fällt, ist es an sich schon interessant. Die Idee in einem Aufsatz von Afshani-Barbay-Chan (FOCS '09), der einen geometrischen Algorithmus diskutiert, berücksichtigt, dass die Algorithmusleistung die Eingabereihenfolge nicht berücksichtigt (was für ihr spezielles Problem relevant ist).

Dies kann wie folgt verallgemeinert werden: Für jede Algorithmuspartition werden die Eingaben in Äquivalenzklassen und die Algorithmusleistung als eine Art kollektive Statistik über die durchschnittliche Leistung für jede dieser Äquivalenzklassen betrachtet.

Bei der Worst-Case-Analyse werden die Eingaben einfach als einzelne Äquivalenzklassen betrachtet und die maximale Laufzeit berechnet. Bei der Durchschnittsfallanalyse wird die einfache Äquivalenzklasse betrachtet, die alle Eingaben umfasst. In der Arbeit von Afshani-Barbay-Chan ist ihr Algorithmus optimal, wenn die Eingabe in Permutationsklassen unterteilt ist (dh die Leistung wird nicht berücksichtigt).

Es ist nicht klar, ob dies zu neuen Paradigmen der Algorithmusanalyse führt. Der Kurs von Tim Roughgarden enthält einige hervorragende motivierende Beispiele und deckt verschiedene Methoden zur Analyse von Algorithmen ab.

Ich habe noch zwei für die Liste, die etwas ähnlich sind.

1. $O(c^n n^{O(1)})$$1 < c < 2$$k$$O(2^k n^{O(1)})$$k$$n$

2. $O(n \log n + k)$$k$

$O(n \log n)$

Es sieht aus wie die parametrisierte Analyse für Polynomialzeitalgorithmen, und es scheint, dass die ausgangssensitive Analyse in diese Kategorie fällt.

Es gibt auch eine Analyse mit " hoher Wahrscheinlichkeit " (für randomisierte Algorithmen), bei der Sie sich für eine bestimmte Situation Sorgen darüber machen, wie gut Ihr Algorithmus die meiste Zeit arbeitet, aber einen kleinen Teil der Zeit vollständig aufgeben können. Dies ist in der Lerntheorie üblich.

Sie können Ihrem Algorithmus Zufälligkeit hinzufügen und ihn mit all den oben genannten kombinieren. Dann erhalten Sie zB die Worst-Case-Laufzeit (Worst-Case-Instanz, gemittelt über alle möglichen Sequenzen zufälliger Münzwürfe im Algorithmus) und die Worst-Case-Laufzeit mit hoher Wahrscheinlichkeit (wiederum Worst-Case-Instanz). aber die Wahrscheinlichkeit über die zufällige Münze wirft im Algorithmus).

Die Bijektivanalyse ist eine Möglichkeit, zwei Algorithmen zu vergleichen (Spyros Angelopoulos, Pascal Schweitzer: Paging und Listenaktualisierung unter der Bijektivanalyse. J. ACM 60, 2013): Algorithmus A ist bei Eingaben der Länge n ungefähr besser als Algorithmus B, wenn es a gibt bijection f der Eingänge der Länge n, so dass A am Eingang x mindestens so gut abschneidet wie B an f (x).

Wettbewerbsanalyse

Wird verwendet, um Online-Algorithmen mit den Offline-Leistungsalgorithmen zu vergleichen. Siehe Wikipedia-Seite . Das Problem mit der Listenaktualisierung ist ein klassisches Beispiel.

Wettbewerbsanalyse Beim Algorithmus zum Ersetzen von Seiten überwiegt eine Methode die andere, da weniger Seiten fehlen. Weniger fehlende Seite zeigt "weniger Laufzeit". Außerdem ist die Konkurrenzanalyse eine Methode, um zwei Methoden relativ zu vergleichen. Ein gutes Nachschlagewerk ist "ONLINE COMPUTATION AND COMPETITIVE ANALYSIS" von Allan Borodin.