[关闭]
@Cy8sac 2020-02-28T04:48:13.000000Z 字数 2127 阅读 54

Analisis of Random QuickSort

数学 CLRS


随机化快排与普通快排唯一的不同是,随机化要求随机选取一个元素(有可能就为头元素)与头元素交换后,再进行“普通”快排。我们想证明随机化快排能保证运行时间在平均运行时间:


证明:

我们先定义一个随机变量T(n),表示算法的运行时间


这里需要注意的是,只有当这些随机数(每个选择主元的事件)相互独立时,等式才成立

为了进行分析,我们首先得知道该选择哪个元素作为主元。

令主元的下标为k,在我们一个特定划分的情况下能得到一个 指示器随机变量(indicator-random-variable) Xk

对这个特定k的 k : n-k-1 划分,我们给予值 1,对于其他情况,我们给予值0.

则Xk的期望(生成一次 k : n-k-1 划分的概率)为


对于T(n)我们则有

这就是T(n)的递归,而每次递归总有n种情况

对于这种麻烦情况,指示器随机变量便体现出了他的优雅,实际上T(n)便等于


此时我们便可开始求T(n)的期望

解释:
(5)~(6): 因为独立于任何其他分化存在(不受分化方式的影响),所以可分别求期望后相乘.If you will,the that would exist for any of the other recursive calls.
(7)~(8):期望的线性性质。
(8)~(9): 其实 ,可以分别写出累加的前几项,发现只是加的顺序反了过来,所以可以合并
(9)~(10):累加的前两项,即T(0)、T(1)为 的复杂度,为了之后方便运算,提取出来与后方的 合并

得到

我们最终想要证明的是

证明之前需要先知道一个定理(这里先不给出证明):


然后我们便可运用代换法(substitution) 证明随机化快排的时间复杂度:

a足够大时



证毕.

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注