Algorytm probabilistyczny albo randomizowany to algorytm, który do swojego działania używa losowości. W praktyce oznacza to, że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w „średnim przypadku”, dzięki czemu „złośliwe" dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie.
Motywacja Załóżmy, że mamy znaleźć literę „a" w tablicy o n elementach, z których połowa jest literami „a", a połowa literami „b". Zwyczajne przeglądanie tablicy może spowodować, że znajdziemy „a" dopiero po sprawdzeniu połowy (½n) elementów, jeśli cały początek tablicy jest wypełniony literami „b". Podobnie przeglądanie tablicy od końca będzie czasochłonne, jeśli cały koniec tablicy jest wypełniony literami „b" itp. Faktycznie dla dowolnej strategii przeglądania tablicy w ustalonym porządku istnieją „złośliwe" przypadki, dla których algorytm działa długo.