Las-Vegas-Algorithmen

von Gruppe 1

Las-Vegas-Algorithmen sind Algorithmen, die sich niemals irren. Allerdings kann es passieren, dass sie kein Ergebnis finden. Dabei gibt es prinzipiell zwei Sorten von Las-Vegas-Algorithmen bezüglich ihrer 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.

todo: Random-Quicksort

• Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.