当前课程知识点:概率论与数理统计 > 应用实例 > 利用期望的计算性质分析快速排序算法的平均计算量 > 利用期望的计算性质分析快速排序算法的平均计算量
所谓排序问题
就是给定n个数字
x1 x2到xn
按照从小到大的顺序将其排列
当然 也可以按照从大到小排序
来提这个问题
二者本质上是相同的
排序问题的应用非常的广泛
对成绩单进行排序
对股票的业绩进行排序等等
不胜枚举
排序问题最简单 最常用的算法是冒泡法
在我们介绍和分析快速排序算法之前
先介绍这种经典算法以便比较
真实地体会到快速算法的快
冒泡法的基本想法
是从数列的第1个元素开始
对元素进行两两比较
如果前面的数字大于后面的数字
就交换它们的顺序 否则的话
保持原来的顺序不变
这样将全体数字扫描一遍
最右端就得到了整个数列的最大值元素
再对前n-1个元素做同样的操作
得到第二大的元素
依次进行n-1次扫描
就得到了原数列按升序排列的结果
我们用5个实际数字
演示一下冒泡法排序的实现过程
首先考查前两个数字
我们把被比较的数字用红色标出
因为5大于1
所以交换5和1的位置
再考查第2和第3个数字
因为5大于4
所以交换5和4的位置
再继续依次比较第3和第4个数字
5和2因为5大于2
所以交换这两个数的位置
最后看5和8
因为5小于8
所以这两个数字的位置保持不变
不作交换
这样所有的数字依次都扫描了一遍
数列中最大的数字
已经转移到了数列的最右边
把它固定下来
我们用彩色标出
下面对前n-1个数
也就是前4个数做同样的操作
进入第二轮比较
第二轮比较中
最后一个位置固定不变了
依次扫描前n-1个数
首先考查前两个数字
因为1小于4
所以1和4的位置不变
再考查第2,3个数字
因为4大于2
所以交换4和2的位置
再继续依次比较第3,4个数字
4和5因为4小于5
所以4和5的位置不变
这样我们得到了数列中第2大的数字
它已经被交换转移到了
数列的最右边第二个位置
把它固定下来
我们用彩色标出
5和8是数列升序排列的最后两项
下面再对还没有最终确定顺序的
剩下的前n-2个数字做同样的操作
进入第三轮比较
实际上到现在为止
这个数列的顺序已经排好了
但是算法并不知道排序已经完成
算法必须完成全部步骤
才能保证在任何情况下
都能够给出正确的排序结果
算法继续进入第3轮的比较
第三轮比较中
最后两个位置固定不变了
依次扫描前n-2个数
首先考查前两个数字
因为1小于2
所以1和2的位置不变
再考查第2,3个数字
因为2小于4
所以也不用交换
这一轮比较得到了数列中第3大的数字
把它固定下来并用彩色标出
得到4 5和8
是数列升序排列的最后三项
下面再对还没有最终确定顺序的
剩下的前n-3个数字做同样的操作
进入第四轮比较
因为n=5 n-3等于2
所以到第四轮
只剩下两个数字没有最终排定位置
比较1和2 因为1小于2
所以顺序不变
这样就得到了
整个数列最终的升序排列结果
1 2 4 5 8
冒泡法的主要优点的是非常的简单
编写很短的程序
就可以在计算机上实现
而它的主要缺陷是效率不高
对于包含几千 几万个数字的数列
计算机都可以很轻易的
马上得到排序结果
但是对于很大规模的问题
冒泡法效率低的弱点就会暴露出来
下面我们分析一下冒泡法排序的计算量
对n个数字排序
第一轮中n个元素依次两两比较
共需要n-1次比较运算
第二轮需要n-2次比较
依次直到最后第n-1轮
对剩下的两个数字进行比较
总的比较次数为n-1加n-2
一直递减加到1
等于2分之n乘n-1
也就是大约2分之n平方的比较运算
要考察和比较算法的计算效率
还要选取一台计算机
目前世界上最强大的超级计算机
已经可以达到每秒亿亿次的计算量级
对普通计算机能达到每秒万亿次
已经是很强大了
假设我们选取这样一台
每秒能够完成万亿次基本运算的计算机
也就是每秒可以完成
10的12次方量级的加 减 比较等运算
对于10的4次方
也就是1万个数字左右的规模
冒泡法排序的计算量大约是
10的8次方量级
用万亿次计算机进排序几乎不花时间
如果对100万量级的数字
也就是10的6次方量级那么多的数字
冒泡法计算量大约是
10的12次方基本运算
考虑到代码的编辑 解释
数据传输等等因素
总的运行时间
应该肯定可以在几秒之内完成
但如果问题规模继续增大
冒泡法排序的计算时间
可能就很难接受了
例如 google的搜索引擎
需要用到对10的10次方量级
那么多数字进行排序的问题
google搜索能够成功的
主要因素之一
是它能够给予每个网页一个适当的评分
评价其重要性
然后对所有网页
按照重要性评分进行排序
假设总共有100亿个网页
用一台每秒运算量达到万亿次
也就是10的12次方
基本运算的计算机来实现
10的10次方个数字
用冒泡法进行排序
需要的比较运算的次数为
2分之10的20次方
除以计算机的每秒运算量
仅仅用于比较的计算时间
就将达到2分之10的8次方秒
这是多么长的一段时间呢
我们计算一下1年有多少秒
365天乘以24小时乘以3千6百秒
1年共有31536000这么多秒
大约3.15乘以10的7次方秒
2分之10的8次秒比1年还要长
显然冒泡法对这样的问题无能为力
事实上人们早就设计出了
更高效的排序方法
最有效的应该是
上个世纪60年代初
提出的快速排序算法
我们现在引入这一部分附加内容的主题
快速排序算法
快速排序算法是一种随机化的算法
上个世纪60年代初
由英国学者霍尔提出
霍尔也因为这一贡献
荣获了1980年的图灵奖
实际上这一巧妙算法的思想
更早几年已经有苏联数学家提出
但是由于学术交流的封闭
前苏联学者的工作
没能及时让更多的人了解
人们现在广泛采用的
快速排序算法的基本形式
是霍尔独立发现的
再重复一下问题
就是要将n个不同的数字按照升序排列
注意 这里强调了n个数字互不相同
实际上如果存在一些相等的数字
也不会带来本质的困难
之所以要求n个数互不相等
主要是为了基本算法描述更方便和清晰
现在我们对算法的主要思想做一描述
首先在n个数中
随机地任选一个数
作为基准元素
将剩下的n-1个数与基准元素进行比较
大于基准元素的数放在右边
小于基准元素的数放在左边
这样基准元素的大小位置就确定了
因为比它小的数都放在它的左边
比它大的数字都放在它的右边
所以基准元素所在的位置
就是它在最终的升序排列中的位置
基准元素将全体数字分成了左右两部分
对左右两个子集合再各选一个基准元素
左边的全体数字
和左边基准元素进行比较
比左边基准元素小的放在它的左边
比左边基准元素大的放在它的右边
右边的全体数字
和右边基准元素进行比较
比右边基准元素小的放在它的左边
比右边基准元素大的放在它的右边
这时新引进的两个基准元素的位置
就是它们在最终的升序排列中的位置
此时基准元素将数列的元素
划分成了更多的部分
在每个子集中再随机选取新的基准元素
将子集内部比其小的放左边
比其大的放右边
按照这样的过程不断进行下去
这样新增的基准元素越来越多
也就是得到最终位置的元素越来越多
当所有元素都排定位置时
算法结束
下面我们还是通过一个实际的数列
演示快速排序算法的实现过程
帮助同学们真正理解快速排序算法
我们考察这样一个包含9个数字的数列
将其中数字按升序排列
快速排序算法的第一步
是在9个数字中
随机选择一个作为基准元素
假设选定的是4这个数
将它标为紫色以示区分
然后依次将3 7 8 5 2 1 9 6等
数列中的其他数字
与基准元素4进行比较
3 2 1比4小
放在了它的左边
而7 8 5 9 6比4大
放在了它的右边
经过这一步
选为基准元素的4这个数字
它在整个数列的
升序排序中的正确位置已经确定
然后进入第二步
先在3 2 1中随机选择一个数
假定选到的是1
染为绿色
将3和2依次和1比较
比1小的放左边
比1大的放右边
3和2都比1大
所以都放在了1的右边
再在7 8 5 9 6中随机选择一个数
假定选到的是8
仍然染为绿色
将7 5 9 6依次与8进行比较
比8小的是7 5 6放在了左边
比8大的是9放在了右边
这样完成了第二步
此时第二步中
选为基准元素的数字1和8
它们在最终的升序排列中的位置
也已经正确的确定了
到此为止
曾经选定为基准元素的
3个元素的位置已经确定
此时基准元素将数列划分为了3部分
分别是3 2组成的一部分
7 5 6组成的一部分
和单个数字9组成的一部分
然后进入第三步
在被先前的基准元素划分出的各部分
再各自随机地挑选一个基准元素
这一部分中比它小的放左边
比它大的放右边
假定表为蓝色的三个数3 6 9
是每一部分选定的新的基准元素
在各部分中
比基准元素小的放在它左边
比基准元素大的放在它右边
就得到了右边的结果
这时蓝色的基准元素
已经得到了它们各自的正确位置
而被基准元素划分出的各部分
至多只剩下一个数字
这些数字的位置
也已经是最终升序排列的正确位置
这时每个元素都被排定了位置
就完成了整个排序算法
为了分析快速排序算法的总的计算量
我们将一列数字表示为星号
算法过程中成为基准元素的数字
就被染上一种颜色
第1步选定1个基准元素
染为紫色
经过与其他元素进行比较后
它将整个数列划分为两部分
并且这个基准元素的位置
就是它在整个按升序排列的
最终结果中的位置
在今后的步骤中不再变化
第2步
在两部分中各选一个基准元素
得到2个新的基准元素
染为绿色
比较后已染色的元素
将整个数列划分为4部分
这2个新的绿色的基准元素的位置
就是它们在整个按
升序排列的最终结果中的位置
在今后的步骤中不再变化
第3步
在四个部分中各选一个基准元素
又得到4个新的基准元素
染为青蓝色
比较后将整个数列分为8个部分
这一步得到的4个新的基准元素的位置
也是它们在整个按升序排列的
最终结果中的位置
在今后的步骤中不再变化
这样一直做下去
每一步的新的基准元素的数目
大体上会翻倍
到第m步
大约会得到2的m-1次方个
新的基准元素
第m步后
总的基准元素的个数
可能达到1加2加2的平方
一直加到2的m-1次方个
即总和为2的m次方减1个
当这个数等于n时
就意味着所有的数字都排定了顺序
这时m大约等于log2n
因为每一步进行的比较次数不超过n次
所以排定所有数字所需的
全部比较次数不超过n乘log2n次
但是要意识到
上述分析是一种非常理想的情形
也就是每一步基准元素的个数都会翻倍
这就意味着每一个基准元素
都恰好选到了所在数据段中位数
附近大小的数字
而如果是极端坏的情况
每一次基准元都选到了最大
或最小的数字
则每一步只确定一个元素的位置
需要n-1步
才能确定所有数字的顺序位置
这时快速排序算法的计算量
就与冒泡法相同了
按照最优情况的计算量
对100亿个网页的得分进行排序
总的比较运算的次数
不超过10的10次方
乘以10倍的log2 10
用万亿次计算机计算
不会超过1秒钟
而最快情况下
快速算法的计算量与冒泡法相同
还是几乎无法有效得到排序结果
因为快速算法的执行过程
是具有随机性的
所以人们想了解
用快速排序算法对n个数字进行排序
到底运行计算量
是nlogn量级的可能性大
还是达到n平方量级的可能性大
事实上
绝大多数执行过程
是nlogn量级的计算量
只有极少数情况
会进行n平方量级的比较
而且可以证明
快速排序算法整个过程所做的
平均意义下的比较次数
是nlogn量级的
下面给出算法分析的定理和它的证明
现在证明快速排序算法
平均比较次数的分析结果
给出如下定理
假设利用随机化快速排序算法
对n个互不相同的数x1 x2
到xn进行排序
每一次都从所有可能的元素中
独立且均匀地选取基准元素
那么所做比较次数的期望
为2n倍的ln(n)
在加与n同量级的一个数
大O(n)的意思就是
与n的比值在常数范围内
下面证明这一结论
首先将x1 x2
到xn按照升序排列后的结果
表示为y1 y2到yn
也就是y1 y2到yn与x1 x2
到xn具有相同的值
并且按照升序排列
有y1小于y2小于y3等等小于yn
对于所有1到n之间不同的
两个角标i和j
假设i小于j
定义一个随机变量Xij
如果算法过程中
yi与yj进行了比较
就令Xij等于1
否则Xij等于0
这里要注意的是
在整个快速排序算法的实现过程中
每两个数之间
或者进行过1次比较
或者没有进行过比较
两个数字发生比较的时候
这两个数中间一定有一个数
是当时所考察子集中选定的基准元素
另一个数与它比较后
或者放在其左边
或者放在其右边
基准元素与子集中所有元素进行比较后
其位置即得到确定
就固定下来
今后不会再参与比较
这样总的比较次数
就可以表示为全体可能的不同的
yi和yj数对
对应的Xij的求和总数
全体不同的数对共有2分之n乘n-1个
这也说明比较次数
最多可达到2分之n乘n-1次
不会超过这个数
利用期望的线性性
即随机变量求和的期望
等于随机变量期望的求和
总的比较次数X的期望即等于
对1到n之间取值的
所有不同的数对i j
对Xij的期望求和
我们仔细考察一下Xij的期望
按照Xij的定义
它刻画的是yi与yj
是否发生过比较的情况
发生过比较Xij取值为1
否则为0
考虑升序排列y1到yn中
yi到yj的这一段数字
当yi与yj发生比较时
yi与yj中必然有一个是yi y(i+1)
直到yj这j-i+1个在升序排列中
连续出现的一段数字中的
第一个被选为基准元素的数字
因为如果yi和yj都不是这个集合中
第一个被选为基准元素的数字
那么这些数字中第一个被选为
基准元素的一定在中间的某个位置
这个基准元素一定会将
yi和yj阻隔在它的左边和右边
从而使得yi和yj
失去相互比较的机会
此时Xij必然为0
所以Xij等于1的概率
就等于从yi到yj的j-i+1个数中
选到yi或yj的概率
因为被选为基准元素是等可能的
所以这个概率等于j-i+1分之2
Xij的期望就等于j-i+1分之2
将Xij的期望表达式代入求和式
考虑到j-i+1分之2
从j等于i+1到n求和
就等于2分之2加3分之2
一直加到n-i+1分之2
所以求和式可以写成
k从2到n-i+1对k分之2求和
然后交换求和顺序
等于k从2到n
对k的不同取值
i从1到n-k+1求和
再对k求和
内层求和与i无关
对所有k
内层求和都等于
n-k+1倍的k分之2
然后进一步整理
提出2倍的n-1
再整理提出2倍的n乘k分之1
k从1到n求和
加一些剩余项
考虑到k从1到n
k分之1求和等于ln(n)
加某个常数量级的数
所以得到求和等于
2n倍的ln(n)加一个n的同阶项
这样就证明了定理结果
快速排序算法的
平均计算量是nlnn量级的
所以绝大多数情况下
它都能较快地得到排序结果
-随机试验与随机事件
-古典概型
--1.2 古典概型
--第一周:古典概型
-事件间的关系与事件的运算
--第一周:事件间的关系与事件的运算
-两个著名的例子
--第一周:两个著名的例子
-讲义
-条件概率
--2.1 条件概率
--第二周:条件概率
-有关条件概率的三个重要计算公式
--第二周:有关条件概率的三个重要计算公式
-事件的独立性
--第二周:事件的独立性
-应用实例
--2.4 应用实例
--第二周:应用实例
-网球比赛胜率的计算
--Video
-讲义
-随机变量及分布函数
--第三周:随机变量及分布函数
-离散型与连续型随机变量
--第三周:离散型与连续型随机变量
-分布函数的性质与特殊的例子
--第三周:分布函数的性质与特殊的例子
-概率论所需微积分要点回顾
--第三周:概率论所需微积分要点回顾
-讲义
-二项分布与负二项分布
--第四周:二项分布与负二项分布
-泊松分布
--4.2 泊松分布
--第四周:泊松分布
-几何分布与指数分布
--第四周:几何分布与指数分布
-正态分布
--4.4 正态分布
--第四周:正态分布
-讲义
-随机变量函数的分布
--第五周:随机变量函数的分布
-随机变量的数学期望
--第五周:随机变量的数学期望
-随机变量的方差
--第五周:随机变量的方差
-原点矩与中心矩
--第五周:原点矩与中心矩
-期望和方差的一些补充性质
--第五周:期望和方差的一些补充性质
-讲义
-二项分布与泊松分布的期望与方差
--第六周:二项分布与泊松分布的期望与方差
-几何分布的期望与方差
--第六周:几何分布的期望与方差
-均匀、指数和正态分布的期望与方差
--第六周:均匀、指数和正态分布的期望与方差
-随机变量数学期望的应用实例
--第六周:随机变量数学期望的应用实例
-快速排序算法的平均计算量分析
--Video
-讲义
-多维随机变量
-第七周:多维随机变量
-常见多维随机变量举例
--第七周:常见多维随机变量举例
-随机变量的独立性
--第七周:随机变量的独立性
-独立随机变量期望和方差的性质
--第七周:独立随机变量期望和方差的性质
-讲义
-条件分布
--8.1条件分布
--第八周:条件分布
-条件期望
--8.2 条件期望
--第八周:条件期望
-全期望公式(上)
--第八周:全期望公式(上)
-全期望公式(下)
--第八周:全期望公式(下)
-讲义
-随机变量函数的期望
--第九周:随机变量函数的期望
-协方差
--9.2 协方差
--第九周:协方差
-相关系数
-- 9.3 相关系数
--第九周:相关系数
-相关与独立
--第九周:相关与独立
-讲义
-独立随机变量和的分布
--第十周:独立随机变量和的分布
-独立正态分布和的分布
--第十周:独立正态分布和的分布
-最大值、最小值分布
--第十周:最大值、最小值分布
-顺序统计量
--第十周:顺序统计量
-讲义
-正态分布的相关与独立
--第十一周:正态分布的相关与独立
-边缘密度均为正态,联合分布不是二元正态的例子
--第十一周:边缘密度均为正态,联合分布不是二元正态的例子
-二项分布的正态近似
--第十一周:二项分布的正态近似
-正态近似计算实例
--第十一周:正态近似计算实例
-讲义
-大数定律
--12.1大数定律
--第十二周:大数定律
-中心极限定理
--第十二周:中心极限定理
-蒙特卡洛(Monte Carlo)算法
-伪随机数和随机模拟
-讲义
-统计学实例
-总体与样本
-常用统计量
--第十三周:常用统计量
-三种重要的统计分布和分位数
--第十三周:三种重要的统计分布和分位数
-讲义
-参数的矩估计
--第十四周:参数的矩估计
-参数的极大似然估计
--第十四周:参数的极大似然估计
-参数点估计的无偏性和有效性
--第十四周:参数点估计的无偏性和有效性
-参数点估计应用实例
--第十四周:参数点估计应用实例
-讲义
-区间估计的基本思想
--第十五周:区间估计的基本思想
-区间估计的构造方法
--第十五周:区间估计的构造方法
-两个正态总体的区间估计
--第十五周:两个正态总体的区间估计
-大样本置信区间
--第十五周:大样本置信区间
-讲义
-假设检验问题的提示和标准步骤
--第十六周:假设检验问题的提示和标准步骤
-假设检验问题的两类错误和P值
--第十六周:假设检验问题的两类错误和P值
-单个正态总体参数的假设检验
--第十六周:单个正态总体参数的假设检验
-拟合优度检验
--第十六周:拟合优度检验
-讲义
-利用条件概率计算网球比赛胜率
-利用期望的计算性质分析快速排序算法的平均计算量
-讲义
-事件
--事件
-分布函数
--分布函数
-正态
--正态
-指数与二项
--指数与二项
-随机变量函数的分布
-指数分布期望
--指数分布期望
-切比雪夫不等式
--切比雪夫
-二元离散
--二元离散
-协方差
--协方差
-二元特征
--二元特征
-统计量
--统计量
-无偏估计
--无偏估计
-点估计
--点估计
-假设检验
--假设检验
-选择
--选择
-填空
--填空
-大题
--大题