快速排序法 平均情况时间复杂度平均情况我知道是nlog(n),我想请问这个结果是怎么推出来的?

平均是nlogn,最差是o(n^2，近乎排好序的前提下)，平均时间需要用到概率论的知识．

这个有一些难度．

首先

1. 给定任何大小为n的数组，任何元素被先为主元的概率都是1/n,因此我们可以定义一个指示器随机变量Xi=I{第i小的元素被选为主元}．(指示器随机变量就是条件成立则为1,否则为0的随机变量)．那么E[Xi]=1/n(因为每个被选的概率都为1/n)

2. 将T(n)划分可有下面n种划分法

   T(n)=T(0)+T(n-1)+o(n) 如果0:n-1划分

　 T(1)+T(n-2)+o(n)如果1:n-2划分

．．．．．．

T(n-1)+T(0)+o(n)如果n-1:1划分．

可以将上面的一共n种可能性写到一起去：

这就是Xk指示器随机变量强大的地方，它可以只使符合条件的一个留下，其它的全筛掉(Xk=0则筛掉其它)

3.现在开始化简上面的式子：这里需要一点数学的化简，还是比较好懂的．



倒数第二步的两个1/n累加式是倒序相等，所以可以变成2/n.现在需要将k=0,1的情况吸收到o(n)中去，这是没有问题的，因为它比o(n)低阶．

4.这里还需要用到一个事实：



这个事实可以用拆分法和积分法证明，这里略去．

接下来就是用替换法证明快排的平均时间效率为nlogn了.


5.

这里先证明基本情况，当a取足够大的值，而k取足够小的值，则可以使下面的式子成立。E[T(k)] <= aklgk(这是一个事实，当k足够小时，这个式子恒成立，类似数学归纳法的初始条件．)

所以



当使()取>0的数，就成立，证完收工．

楼主查收！