灵鹊做题网快速排序法 平均情况时间复杂度
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：数学作业 时间：2024/05/08 13:27:45
快速排序法 平均情况时间复杂度
平均情况我知道是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种可能性写到一起去：
这就是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的数，就成立，证完收工．楼主查收！
排序技术中 冒泡法和快速排序法的最坏情况下的比较次数是多少 其时间复杂度分别是多少
数据结构中堆排序,快速排序,归并排序排序的时间复杂度顺序快慢依次是什么?
如果在考研的数据结构填空题中出现快速排序的时间复杂度是填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)进行升序排序的序列变化情况.