快速排序法 平均情况时间复杂度
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/09/03 03:09:53
快速排序法 平均情况时间复杂度
平均情况我知道是nlog(n),我想请问这个结果是怎么推出来的?
平均情况我知道是nlog(n),我想请问这个结果是怎么推出来的?
快速排序时间复杂度可以写成
T(n)=2T(n/2)+n,这个求解就是T(n)=nlogn
再问: 这个公式应该是最好情况下的吧 我想问的是平均情况...
再答: 平均是nlogn,最差是o(n^2,近乎排好序的前提下),平均时间需要用到概率论的知识.这个有一些难度.
首先 给定任何大小为n的数组,任何元素被先为主元的概率都是1/n,因此我们可以定义一个指示器随机变量Xi=I{第i小的元素被选为主元}.(指示器随机变量就是条件成立则为1,否则为0的随机变量).那么E[Xi]=1/n(因为每个被选的概率都为1/n)将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的数,就成立,证完收工.楼主查收!
T(n)=2T(n/2)+n,这个求解就是T(n)=nlogn
再问: 这个公式应该是最好情况下的吧 我想问的是平均情况...
再答: 平均是nlogn,最差是o(n^2,近乎排好序的前提下),平均时间需要用到概率论的知识.这个有一些难度.
首先 给定任何大小为n的数组,任何元素被先为主元的概率都是1/n,因此我们可以定义一个指示器随机变量Xi=I{第i小的元素被选为主元}.(指示器随机变量就是条件成立则为1,否则为0的随机变量).那么E[Xi]=1/n(因为每个被选的概率都为1/n)将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种可能性写到一起去:
![](http://img.wesiedu.com/upload/a/5c/a5c697f951cf5a23d95e8f823caea2cb.jpg)
![](http://img.wesiedu.com/upload/c/cd/ccdb1f0e7c92afdecc808fc6eb2df91f.jpg)
![](http://img.wesiedu.com/upload/b/58/b584deffdb353baa04aec0bfe2aa8860.jpg)
5.这里先证明基本情况,当a取足够大的值,而k取足够小的值,则可以使下面的式子成立。E[T(k)] <= aklgk(这是一个事实,当k足够小时,这个式子恒成立,类似数学归纳法的初始条件.)所以
![](http://img.wesiedu.com/upload/3/e5/3e50d26042a0609211542b31bdd80499.jpg)
排序技术中 冒泡法和快速排序法的最坏情况下的比较次数是多少 其时间复杂度分别是多少
数据结构中堆排序,快速排序,归并排序排序的时间复杂度顺序快慢依次是什么?
如果在考研的数据结构填空题中出现快速排序的时间复杂度是填n的平方,还是n倍log以二为底n的对数
数据结构中怎么计算时间复杂度
算法的时间复杂度计算问题
C语言中算法时间复杂度
数据结构时间复杂度的计算求解
算法设计题:计算时间复杂度
串的模式匹配算法中的BRUTE FORCE算法在最好情况下的时间复杂度为什么是O(n+m)而不是O(m)?其中m是模式.
求下列各程序段的时间复杂度.
下面程序段的时间复杂度为_____.(n>1)
2.给出利用快速排序方法对线性表(25,84,21,47,15,27,68,35,20)进行升序排序的序列变化情况.