Las-Vegas-Algorithmus

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 $\geq {\frac {1}{2}}$ korrekt ist und der Algorithmus zugleich mit einer Wahrscheinlichkeit $\leq {\frac {1}{2}}$ 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