快速排序平均时间复杂度的推导
快速排序作为一种随机算法，无法用常规方法计算时间复杂度。本文记录了一种推导方法。
快速排序作为一种随机算法，无法用常规方法计算时间复杂度。
wiki上快速排队平均时间复杂度的分析有三种，本文记录了一种推导方法。
先把伪码快速排序，方便查阅参考。
快速排序(int L，int R，int array[]){ 0
if(L=R){ 0
返回；
}
int pivot=RANDOM(L，R)；
int l=L，r=R
int support _ array[array . length()]
for(I=L-R){ 0
if(I==pivot){ 0
返回；
}
else if (array[i]=array[pivot]){
support _ array[l]=array[I]；
}
else {
support _ array[r-]=array[I]；
}
}
support _ array[l]=array[pivot]；
array-support _ array；
快速排序(L，l-1，数组)；
快速排序(l 1，R，数组)；
}
n是序列的长度。对于长度为n的序列，我们总共需要调用n次quicksort函数。我们提出序列中的元素与枢纽之间的比较操作(代码第8-18行，以下简称“比较”)进行统筹考虑。除了比较运算，函数每次调用的时间复杂度为O(1)，设x为函数被调用n次的比较总数，快速排序的时间复杂度为t (n
以下是x的计算过程。
设ei为原序列中第几个最小的数，ej为第几个最小的数，j为I，在对原序列进行完全排序的整个过程中，每个位置都会被选中一次作为支点。Ei和ej将被比较。当且仅当在ei的子序列中，ei 1，ei 2，ej-1，ej(根据假设，这是一个非降序序列)，首先在这个子序列中选择ei和ej中的一个作为pivot，否则选择它们之间的一个数字作为pivot，经过一轮比较，ei和ej将被分成两个子序列。P(ei和ej比较)=2/(j-I ^ 1)当我们使用的随机数生成算法能够保证每个数被选为枢纽的概率相等时。设Y为ei和ej的比较次数，Y=0或1，Y的期望值计算如下
\[P(Y=1)=P(e_i和e_j比较)=2/(j-i 1)
\]\[E(Y)=P(Y=1) * 1=2/(j – i 1)
\]但是，在序列中，任意两个比较时间的期望值是2/(j-I ^ 1)
X是比较的总数，那么X的预期表达式是
\[e(x)=\sum_{i=1}^{n-1}\sum_{j=i 1}^{n}2/(j-i 1)
\]后半部分的和为调和级数，调和级数的和公式如下
\[1 1/2 1/3 .1/n=ln(n 1)
\]用于计算E(x)
\[\ sum _ { j=I 1}^{n}2/(j-i 1)=2 *[ln(n-I 1)-1]=o(logn)
\]\[e(x)=\sum_{i=1}^{n-1}o(logn)=o(nlogn)
\]\[T(n)=O(n x)=O(n nlogn)=O(n nlogn)
\]此时，已经推导出快速排序的平均时间复杂度O(nlogn)。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/88688.html