Las-Vegas-Algorithmen

Wiki-Quelltext dieser Seite.

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, jedoch nur im offenen Intervall <math>\left(\frac{1}{2} , 1\right)</math>. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.