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:

1. 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

1. 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.