Las-Vegas-Algorithmus

Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert. 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. 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 . Es gibt also Fälle, in denen der Algorithmus das Ergebnis "?" ausgibt.

Siehe auch

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

See also: Las-Vegas-Algorithmus, Komplexitätstheorie, Liste von Algorithmen, Monte-Carlo-Algorithmus, Pivotelement, Quicksort, Randomisierter Algorithmus, Zeitkomplexität