Kann eine minimal mögliche Effizienz nachgewiesen werden?

Ist es bei einem gegebenen Problem möglich zu beweisen, wie die beste Worst-Case-Effizienz eines Algorithmus zur Lösung dieses Problems wäre?

Nehmen wir zum Beispiel das Problem des Sortierens eines Arrays.

Viele der einfacheren Sortieralgorithmen haben eine Worst-Case-Effizienz von wie z. B. Quick Sort und Bubble Sort. Es gibt jedoch andere Algorithmen wie Timsort und Smoothsort mit , was effizienter ist.$O(n^2)$$O(n \log n)$

Kein anderer Algorithmus (meines Wissens) konnte ein Array effizienter sortieren als . Kann man beweisen, dass es keinen anderen Algorithmus gibt, der effizienter ist?$\Theta(n\log n)$

Wenn es eine Möglichkeit gibt, für Sortieralgorithmen zu beweisen, ob ein effizienterer Algorithmus vorhanden ist, gilt dies auch für andere Probleme?

Es gibt sicherlich Möglichkeiten zu zeigen, dass bestimmte Algorithmen eine bestimmte Zeit benötigen oder bestimmte Datenstrukturen eine bestimmte Menge an Platz benötigen. Ein üblicher Weg ist die Verwendung der Informationstheorie.

Ein unsortiertes Array ist eine Permutation des sortierten Arrays. Es gibtmögliche Permutationen. Die Aufgabe des Sortierens im informationstheoretischen Sinne besteht darin, genau herauszufinden, um welche Permutation es sich handelt.$n!$

Um eine Zahl zwischen und übertragen, müssen Informationsbits übertragen werden. Um eine Permutation von Elementen zu übertragen, ist daherInformationsbits. Nach Stirlings Näherung stellt sich heraus, dass dies Bits .$1$$m$$\log_2 m$$n$$\log_2 n!$$n \log_2 n + O(\hbox{low order})$

Eine binäre Vergleichsoperation erkennt ein Informationsbit. Daraus folgt, dass jeder Sortieralgorithmus, der nur eine binäre Vergleichsoperation verwendet, mindestens Vergleiche durchführen muss. Wenn wir davon ausgehen, dass ein Vergleich eine konstante Zeit in Anspruch nimmt, bedeutet dies, dass die Sortierung mindestens Zeit in Anspruch nehmen muss .$n \log_2 n + o(n \log n)$$\Omega(n \log n)$

Eine Radix-Sortierung könnte dies übertreffen, indem mehr als ein Informationsbit pro Abfrage ermittelt wird.

Ein ähnliches Argument zeigt, dass die binäre Suche optimal ist. Sie versuchen, eine Zahl zwischen und , was bedeutet, dass Informationsbits ermittelt werden. Wenn Ihre Abfrageoperation ein Informationsbit zurückgibt, benötigen Sie mindestens Abfragen, um ein Element zu finden.$1$$n$$\log_2 n$$\log_2 n$

Ähnlich verhält es sich mit der Raumnutzung. Angenommen, Sie müssen eine Permutation im Speicher speichern. Nach einem identischen Argument erfordert dies mindestens Speicherbits. Da Sie Bits benötigen , um eine Ganzzahl zwischen und zu speichern , können Sie im Wesentlichen nichts Besseres tun, als Ganzzahlen zu speichern .$n \log_2 n + o(n \log n)$$\log_2 n$$1$$n$$n$

Sortierung in der Tat hat sich gezeigt , zumindest nehmen Zeit , wenn die Sortierung auf Vergleiche basiert. Für Ganzzahlen fester Größe gibt es schnellere Methoden (Radix-Sortierung).$O(n \log n)$

Das Sortieren ist jedoch eines der seltenen Probleme, bei denen dies durchgeführt wurde. Im Allgemeinen kennen wir keine Untergrenzen für die zeitliche Komplexität der meisten Probleme. Wenn wir zum Beispiel wissen, dass eine Untergrenze für vollständige Probleme ist, dann wissen wir, dass . Ein solches Ergebnis wurde jedoch nicht nachgewiesen, so dass gegen ein Rätsel bleibt.$O(2^n)$$NP$$P \neq NP$$P$$NP$

Für Probleme im Allgemeinen gibt es keinen Algorithmus, der eine Darstellung eines Problems aufnehmen und eine Untergrenze für seine zeitliche Komplexität zurückgeben kann. Dies liegt daran, dass die Menge solcher Komplexitäten eine Indexmenge wäre: Das heißt, sie repräsentiert eine Eigenschaft von Sprachen (Problemen), nicht von Algorithmen. Es gibt ein Ergebnis namens Rices Theorem, das besagt, dass solche Mengen unentscheidbar sind.

Im Allgemeinen ist dies möglich, aber es ist wichtig, dass Sie dabei das Berechnungsmodell angeben. Ein bekanntes klassisches Beispiel ist das$\Omega(n \log n)$an die Sortierung im Entscheidungsbaummodell gebunden. Um die im Entscheidungsbaummodell nachgewiesene Sortieruntergrenze zu umgehen, dürfen Sie keine Vergleiche durchführen.

Ein weiteres Beispiel ist das Zellsondenmodell . Zusätzlich zu den Beispielen auf Wikipedia können Sie sich zB Fredman-Saks (STOC'89) ansehen . Dies ist ein starkes Modell; Wenn Sie eine Grenze mit einem Algorithmus überwinden möchten, dürfen Sie nicht auf den Speicher zugreifen.