脚本宝典收集整理的这篇文章主要介绍了快速排序平均时间复杂度O(nlogn)的推导，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

快速排序作为随机算法的一种，不能通过常规方法来计算@R_2_1304@

wiki上有三种快排平均时间复杂度的分析，本文记录了一种推导方法。

先放快速排序的伪代码，便于回顾、参考

quicksort(int L, int R, int array[]) {
    if (L >= R) {
    	return;
    }
    int pivot = RANDOM(L, R);
    int l = L, r = R;
    int support_array[array.length()]
    for (i = L -> R) {
    	if (i == pivot) {
    		return;
    	} 
    	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;
    quicksort(L, l-1, array);
    quicksort(l+1, R, array);
}

n为序列长度，对于长度为n的序列，我们总共需要调用n次quicksort函数，我们将序列中元素与pivot的比较操作（代码8-18行，以下简称为“比较”）提出来总体考虑，每调用一次函数，除开比较操作，时间复杂度均为O(1)，设x为n次调用函数总共的比较次数，快排的时间复杂度T(n) = O(n+x)

以下为x的计算过程

设e_i为原序列中第i小的数，e_j为第j小的数， j > i。在对原序列完整排序的整个过程中，每一个位置都会被选作为pivot一次。e_i与e_j会被比较，当且仅当在e_i, e_i+1, e_i+2 , ... , e_j-1, e_j 这个子序列中（按照假设，此为非降序序列），e_i与e_j其中一个最先在这个子序列中被选为pivot ，否则一个大小介于他们中间的数被选为pivot，在一轮比较过后，e_i和e_j就会被分在两个子序列中，没有被比较且以后也不会被比较。当我们使用的生成随机数算法能保证每个数被选中为pivot的概率相等时，P(e_i与e_j被比较) = 2 / ( j - i + 1 )。设Y为e_i与e_j比较的次数，Y = 0 或 1, Y的期望计算如下

而在序列中，任意两项比较次数的期望均是 2 / ( j - i + 1 )

x是总共比较次数，则x的期望的表达式为

后半部分的求和是调和级数(harmonic series)， 调和级数求和公式如下

用于计算E(x)

到此，快速排序的平均时间复杂度O(nlogn)也就推导完成了。

脚本宝典总结

以上是脚本宝典为你收集整理的快速排序平均时间复杂度O(nlogn)的推导全部内容，希望文章能够帮你解决快速排序平均时间复杂度O(nlogn)的推导所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。