效应表现为实际执行结果与理论上的最优解或期望结果的差异。第2，3种情况中，随机的影响还可能伴随有对执行流程的影响。我们后面的讨论就分这三种情况进行。在讨论之前，我们还要澄清一个问题。随机化和“运气”由于随机化算法的执行情况受到不确定因素的支配，因此即使同一个算法在多次执行中用同样的输入，其执行情况也会不同，至少略有差异。差异表现为出解速度快慢，解正确与否，解的优劣等等。例如：一个随机化算法可能在两次执行中，前一次得到的解较优，后一次的较劣。现在的问题是：在大多情况中，尤其是竞赛时，对于同样的输入，只允许程序运行一次，根据运行结果判定算法的好坏。如此一来，我们就会把出劣解的一次运行归咎于运气不佳，反之亦然。然而，比赛比的是谁的算法更有效，而不是谁的运气更好。既然我们使用了随机函数，我们就无法摆脱运气的影响，所以我们的目标是尽量将运气的影响降到最低。也就是说，我们必须使算法的执行情况较为稳定。因此，在接下来的对算法的分析中，我们将从以下四方面分析算法的性能。1．时间效率；2．解的正确性；3．解的优劣程度解与最优解的接近程度；4．稳定性，即算法对同样的输入的执行情况的变化。变化越小则越稳定。非随机化算法的稳定性为100，随机化算法的稳定性属于区间0100。通常，只要算法的程序实现所用的空间不超过内存限制，我们就不必刻意提高算法的空间效率，所以我们省去了空间效率这项分析。上面第4项的“稳定性”可以是算法的平均时间复杂度，也可以是执行算法得到正确解的概率，还可以是实际解达到某一优劣程度的概率。“稳定性”这一项是评判随机化算法好坏的一个重要指标。
2．执行结果确定的随机化算法
在这一节中，我们以快速排序和它的随机化版本为例，讨论执行结果确定的随机化算法。根据引言中的分析，一个随机化算法的执行结果确定，则它的执行流程必会受随机的影响，影响多表现在算法的时间效率上。所以在下面的讨论中，我们省去了对算法执行结果正确性和优劣的分析。快速排序算法
IOI’99中国集训队优秀论文选37
f论随机化算法的原理与设计
快速排序是一种我们常用的排序方法，它的基本思想是递归式的：将待排序的一组数划分为两部分，前一部分的每个数不大于后一部分的每个数，然后继续分别对这两部分作划分，直到待划分的那部分数只含一个数为止。算法可由以下伪代码描述。QUICKSORTAlohi1iflohi2pPARTITIONAlohi3QUICKSORTAlop4QUICKSORr