Las-Vegas-Algorithmus

Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert. Es gibt dabei 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 eine Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist.
• Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert, jedoch nur im offenen Intervall $\left]\frac{1}{2} , 1\right[$. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.

Siehe auch

• Monte-Carlo-Algorithmus
• Komplexitätstheorie
• Liste von Algorithmen