U ovom poglavlju izučavamo randomizirane algoritme koji mogu da na slučajni način biraju sledeći korak za izvršavanje prilikom obrade ulaznih podataka. Da bi slučajno odabrali narednu granu izvršavanja, podrazumevamo da ovi algoritmi to rade na osnovu slučajnog izbora elementa iz neke kombinatorne strukture kao što su skupovi ili grafovi. Tipično, ovi algoritmi mogu izabrati slučajni element iz datog skupa, ili izabrati slučajnu granu grafa sa datim osobinama, ili generisati slučajnu permutaciju od svih mogućih permutacija date dužine. Ne samo to, sve ove operacije se smatraju osnovnim operacijama koje se izvršavaju za neko jedinično vreme.
Uopšteno govoreći, neki algoritam nazivamo randomiziranim ako je njegovo izvršavanje određeno ne samo ulaznim podacima, nego i slučajnim ishodima nekog eksperimenta. Ovi ishodi se obično simuliraju „slučajnim” brojnim vrednostima koje se dobijaju kao rezultati determinističkih algoritama. Pri tome, ovi brojevi se statistički ne razlikuju od pravih slučajnih brojeva, pa se zato nazivaju pseudoslučajni brojevi. Naravno, dodatno se podrazumeva da se ovakvi brojevi koji izgledaju slučajno mogu pojedinačno generisati za konstantno vreme.
(Iz knjige Osnove dizajna i analize algoritama, CET & Računarski fakultet, 2008.)
