Jelaskan Algoritme pengacakan dari Algoritma

Algoritme ini membuat pilihan secara acak (atau pseudo-acak). Ia sangat berguna untuk menemukan solusi perkiraan untuk masalah dimana solusi yang pasti tidak praktis (lihat metode heuristik di bawah). Untuk beberapa masalah, diketahui bahwa perkiraan tercepat harus mengikutkan beberapa pengacakan. Apakah algoritme pengacakan dengan kompleksitas waktu polinomial bisa menjadi algoritme tercepat untuk beberapa masalah masih menjadi pertanyaan terbukan yang dikenal sebagai Masalah P versus NP. Ada dua kelas besar dari algoritme ini:

Algoritme Monte Carlo mengembalikan jawaban yang benar dengan probabilitas-tinggi. Misalnya, RP adalah sub-klas dari algoritme ini yang berjalan dalam waktu polinomial)

Algoritme Las Vegas selalu mengembalikan jawaban yang benar, tetapi waktu prosesnya adalah hanya terikat secara probabilistik, misalnya ZPP.