Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert. Der Begriff wurde 1979 von László Babai im Zusammenhang mit Graphenisomorphie als eine Variante von Monte-Carlo-Algorithmen eingeführt.
Es gibt zwei Definitionen für Las-Vegas-Algorithmen und ihre Zeitkomplexität:
Wenn die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert.Die Zeitkomplexität ist in diesem Fall abhängig von einer Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist. Wenn das Ergebnis der Berechnung eines Algorithmus mit einer Wahrscheinlichkeit korrekt ist und der Algorithmus zugleich mit einer Wahrscheinlichkeit kein Ergebnis liefert, dann ist es ein Las-Vegas-Algorithmus.
Beispiel Der folgende Algorithmus liefert garantiert den Index, dessen Arrayelement den Wert 1 annimmt, falls es den Wert 1 gibt. // Las-Vegas-Algorithmus repeat: k = RandInt(n) if A[k] == 1, return k;
Siehe auch Randomisierte Komplexitätsklassen
Einzelnachweise
Kategorie:Algorithmus