Ein
randomisierter Algorithmus (auch
stochastischer oder
probabilistischer Algorithmus) versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw. näherungsweise korrekten Ergebnis zu gelangen. Er bildet somit das Gegenstück zum
deterministischen Algorithmus. Es wird dabei nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Ein Beispiel, das dies zeigt, ist der
AKS-Primzahltest, der zwar deterministisch ist, aber viel ineffizienter und viel schwieriger zu implementieren als beispielsweise der
Primzahltest von Solovay und Strassen.