…мор≥вн≥сн≥ алгоритми. јлгоритми, що розгл¤дались дос≥, називають детерм≥нованими. Ѕ≥льш≥ обчислювальн≥ можливост≥ мають ймов≥рн≥сн≥ алгоритми. ќкр≥м входу , ймов≥рн≥сний алгоритм отримуЇ випадкову дв≥йкову посл≥довн≥сть , дал≥ працюЇ ¤к звичайний детерм≥нований алгоритм ≥ результат роботи подаЇ на вих≥д. ƒовжина випадковоњ посл≥довност≥ залежить в≥д довжини входу.

††††††††††† —л≥д п≥дкреслити, що вих≥д ймов≥рн≥сного алгоритму залежить не лише в≥д входу, а й в≥д випадковоњ посл≥довност≥. ¬ипадкова посл≥довн≥сть вважаЇтьс¤ р≥вном≥рно розпоод≥леною на , тобто кожневибираЇтьс¤ з ймов≥рн≥стю . …мов≥рн≥сний алгоритм розвТ¤зуЇ масову задачу з ймов≥рн≥стю помилки , ¤кщо отримавши на вх≥д ≥ндив≥дуальну задачу , в≥н подаЇ на вих≥д њњ правильний розвТ¤зок з ймов≥рн≥стю не менш н≥ж . ≤ншими словами, вих≥д алгоритму Ї розвТ¤зком ≥ндив≥дуальноњ задач≥дл¤ вс≥х, окр≥м щонайб≥льше †випадкових посл≥довностей .

††††††††††† …мов≥рн≥сн≥ алгоритми ще називають алгоритмами ћонте  арло. Ћас ¬егас алгоритми Ї п≥дкласом алгоритм≥в ћонте  арло. Ћас ¬егас алгоритм розвТ¤зуЇ задачу з ймов≥рн≥стю невдач≥ , ¤кщо на кожному вход≥ в≥н видаЇ або правильний розвТ¤зок ≥ндив≥дуальноњ задач≥, або пов≥домленн¤ (на зразок спец≥ального символу #) про неспроможн≥сть такий розвТ¤зок знайти, причому друге маЇ м≥сце з ймов≥рн≥стю щонайб≥льше . ћожна вважати що Ћас ¬егас алгоритм взагал≥ не помил¤Їтьс¤, лише часом утримуЇтьс¤ в≥д поданн¤ на вих≥д розвТ¤зку.

††††††††††† „ас роботи ймов≥рн≥сного алгоритму на вход≥ означуЇтьс¤ ¤к максимальна пок≥льк≥сть крок≥в, ¤к≥ алгоритм робить на цьому вход≥ з використанн¤м випадковоњ посл≥довност≥ (≥нод≥ час роботи ймов≥рн≥сного алгоритму означують ¤к середню, а не максимальну к≥льк≥сть крок≥в). “аким чином, пон¤тт¤ пол≥ном≥ального часу, ¤ке було введене дл¤ детерм≥новиних алгоритм≥в, переноситьс¤ й на клас ймов≥рн≥сних алгоритм≥в.