Un algorithme aléatoire est un algorithme qui utilise un certain degré d' aléa dans le cadre de sa logique. L'algorithme utilise typiquement des bits uniformément aléatoires comme entrée auxiliaire pour guider son comportement, dans l'espoir d'obtenir de bonnes performances dans le "cas moyen" sur tous les choix possibles d'aléa déterminés par les bits aléatoires; donc soit le temps d'exécution, soit la sortie (ou les deux) sont des variables aléatoires.