随机算法分为两类。
拉斯维加斯:这些算法始终会产生正确或最佳结果。这些算法的时间复杂度基于随机值,并且时间复杂度被评估为期望值。例如,随机化的QuickSort总是对输入数组进行排序,并且QuickSort的最坏情况预期时间复杂度为O(nLogn)。
蒙特卡洛(Monte Carlo):以一定的概率得出正确或最佳的结果。这些算法具有确定的运行时间,通常更容易找出最坏情况下的时间复杂度。例如,Karger算法的此实现产生的最小割概率大于或等于1 / n 2(n是顶点数),并且最坏情况下的时间复杂度为O(E)