大家好,数据结构与算法
这一讲,我们继续学习第一章:概论的内容。
今天我们重点介绍算法的效率度量
那我们涉及的一个算法以后呢,要关心它的时间和空间性能。特别是 它的时间性能
那对于一个算法,我们,如果它分为几个算法段 是顺序的这个四个部分
那显然我们可以发现呢,其中n² 是它最关键的一个部分,特别是n
比较大以后,那其他的部分呢,其实都可以忽略
那因此我们重点关注的就是算法 它的增长率,特别是n到一定规模以后
它是一个什么量级的算法?是线性的,还是n方的,还是指数级的?
那对算法的这么一个理论的度量呢,有利于我们估计这个算法
它是不是在我们可以忍受的时间内求解
算法的复杂性分析里面,最重要的是大O表示法的一个分析
那,我假设算法的复杂性函数是f
如果我能够找到某一个函数g 算法的问题规模n
大于等于n0以后,那我们有一个正数c f(n)≤
cg(n) 那就称f(n)是在集合O(g(n))
也简写为f(n)=O(g(n))
那大O表示法,它表达的是函数增长率的一个上限 也就是说,这个算法
再复杂,那它不会超过g(n)的这么一个量级
这些上限的函数可能有很多个
我们希望能够找到最紧的那一个,那其实呢
还有一个相应的定义是算法的下限,也就是大Ω
那如果是上限和下限是相等的时候呢,那我们就
表达为大θ,那在我们数据结构与算法当中
很多情况下,大Ω和大θ的表示呢基本上是一样的。因此
有很多教材其实就只写大O的表示法,对于非计算机专业的同学来说
我们只要求大家掌握大O表示法就可以了
当你看到大θ的时候你就把它当作大O一样的来理解 那我们看一下大O表示法的图示
那这个大O表示法呢 它对于我们的这个算法的复杂函数f(n)
那我们要找的是一个cg(n),当这个n等于
n。之后呢,我们cg(n)它的这个的增长的这么一个幅度呢
它是要比这个f(n)要大,也就是说
g(n)在f(n)之上,当然我们是成了一个正的系数c
我们看这个图示可以发现呢,当n小于n。的时候呢
在某些情况下可能f(n)它还超过了cg(n)
那这个是没有关系的,我们不关心小规模的这个特殊情况
也是是n足够大的时候呢,g(n)它是f(n)的上界
而且这个时候我们都不关心c具体的取值是怎么样了
也就是说,在算法度量里面我们是找f(n)它的里面那个
阶最大的那一部分,而且它这个前面的系数以及后面的那些
低阶的那些多项式呢,我们都可以给它去掉 那大O表示法,我们怎么来
衡量,那么其实我们就是看这个算法段里面 它的一些基本运算是什么,那像简单的布尔
以及算数运算那都是一个大O(1)的时间
那还有一些简单的I/O,这个简单I/O呢主要 是从内存里面读,那也就是从数组里面
读元素或者是说我们参数的这种传递都是简单的I/O。但是我们不包括
这种键盘文件的这种操作,因为那种是外设的I/O呢
它是非常非常耗时的,而且不可控
那大O表示法它有两个重要的运算规则
首先是加法规则,那如果是有 两个
程序段它的时间复杂度呢分别是f1和f2 那它整体的这个算法呢,我们是
关心最耗时的那一段,也就是我们 取的这两个复杂度里面最大的那一个
那对于顺序结构还有 判断结构以及这种switch的结构呢
都是适应于加法规则,还有一种规则呢就是乘法规则
那也就是,那对于嵌套的程序段,内层循环的
这样的算法代价,然后再跟外层循环 的这种算法代价呢,我们是需要给它乘起来的
那它总共耗费的时间呢就是这两层循环的一个乘积
那乘法规则它适用于for,while
这样的循环结构。那我们看到这个例子你就可以发现我们是一个
双重循环,然后每一重循环呢,它的代价 都是n量级的,然后乘起来呢
就是一个n平方量级的,而且我们可以看到我们关心的是
这算法复杂度它是一个什么样的阶,它的
前面的系数以及后面的低阶的那些项呢
都被忽略掉,那算法渐进分析里面
还有大Ω表示法,它是相对于
大O表示法的,我们关心的是算法的
下界,那也就是说相应的存在
正数c和n。当n≥n。以后呢,我们能够
找到f(n)它是大于等于c乘以g(n)的。也就是说
这个f(n)呢它在g(n)之上
那这种情况我们也简写成f(n)=Ωg(n)
那么当然,当Ω表示法它也是有很多个下界
那我们一般是需要找到一个最紧的一个下界
那当Ω表示法的图示呢,我们可以看到它跟
大O表示法呢是相似的,那也是找到这么一个
n。,当n≥n。以后呢
这个f(n)它是会在cg(n)之上
但是我们忽略掉这个c,我们可以说
这个f(n)它的一个下界呢就是Ωg(n)的
当这个上界和下界 是一样的时候呢,那我们就是一个确界
那采用的是大θ表示法,我们其实 就可以有这么两个不等式来界定f(n)
下面这个下界呢是C1g(n) 上界呢是C2g(n),f(n)呢是处于中间
然后当n≥n。以后呢,这个C1g(n)
和C2g(n)呢把f(n)是夹在中间的
那我们是得到了这个算法的这样的渐进
增长率以后呢,那我们可以来比较一下 各个函数它们增长的曲线
那可以发现呢,这个n呢它是一个 线性增长的,那通常情况下很多算法
都跟它的数据规模n相关,而如果你能够找到logn的算法呢
那就是 比较高效的,但是在某些情况下呢,我们可能是需要一个常数型的算法
例如搜索引擎,它在所有的结果返回的时候,我们是希望能够有
大O(1)的这样的响应速度,那我们会有一些特殊的索引和检索策略
那n乘以log n的增长率是非常接近于
n的,尤其是n的规模比较大的时候,那我们很多排序算法
它是比较高效的,就是因为它是n乘以log n的
而n平方的算法,当n的规模比较大以后呢 它其实也会比较慢,例如我们有一些低效的排序方法
那它们的问题的复杂度是大O(n方)的,这些
算法呢就在n是一百万以上以后呢就不能很好的工作了
那还有些算法它是指数型的,就是2的n 次方的,那这些算法呢就是一些复杂算法,只能处理
n是小规模的情况。我们如果遇到了 一些很差的数据,那就是碰到了最坏情况
那这种情况下呢,我们的算法的时间呢可能会 变得很慢,而如果遇到了很好的数据
,就是最好的情况呢 那我能够快速得到相应的解 大部分情况下呢,我们是这不好不坏的这样的数据
那我们算出来的是算法的平均代价 很多时候我们需要考虑算法在最坏、最好
和平均情况下各是什么样的时间代价 对于这个最好的情况呢,我们可以利用它的一些
特殊的输入情况,然后组合出一些比较好的算法,例如在
我们的排序算法里面,就有这样的情况 那还有对于最坏的情况呢,我们主要是要考虑一些极限情况下
我们是不是能够处理这样的问题的空间,例如我们
有很多软件系统它需要做一些压力测试,其实就是考虑的最坏情况
而平均情况就是在统计意义下 这样的一个算法,它大致是一个什么样的性能
那我们前面介绍过的几个 算法,我们来看一下顺序找K值的这么一个穷举法
那它在最好的情况下它比较的第一个元素 就是要找的那个K值,那只需要大O(1)的时间
而如果是最差的情况,它一直找到最后一个 才找到这个元素,或者是说找到最后一个还没找到
那这种时候呢就是一个最差的情况 那会是大O(n)的时间,那我们如果来看一下它的平均
情况呢,那我们假设这些数值呢是等概率分布的
那这种情况下呢就是K值出现在每个位置的概率都是1/n
那平均情况下它的算法的代价就会是大O(n)的时间
那我们再来看不等概率的情况呢,那我
假设出现在位置1的时间是1/2,出现在位置2呢是1/4
其他位置呢是这么一个公式表达的,那平均 的代价我们就会得到这么一个结果
而这个结果其实在大O的意义下,它还是大O(n)
那我们前面介绍的二分法找K值这么一个递归分治的方法
那这个方法呢它在最好的情况下其实也
是在第一个这个中值呢就是我们要找的这个元素
那它也是大O(1)的这么一个时间 而最坏的情况以及平均的情况怎么样呢?那我们
来看一下二分检索的这么一个例子
那其实我们可以用这么一个决策树来观察二分检索
的性能,最大的检索长度以及失败的检索长度这都是最坏的情况下
我们在这个检索树里面需要下降几层 那这个下降的这个层次呢都是
log n量级的,因此我们最大和失败的这样的检索长度呢
都是log n的,那它的平均检索代价呢 也是大O(log
n)的,在这里我们注意 我们的表达并没有给出log
n的底 那在算法复杂性分析里面,我们很多情况下都是以2为
底的,而因为我们有一个换底公式
所以呢,对于用10或者是其他的底的表达
在大O意义下都是一样的,因为我们并不关心它的系数是什么
算法的时间代价呢跟
空间代价它的分析的方法,表达的方法其实是类似的,也就是说我们刚才介绍的主要是从
时间的角度来说了,大O、大Ω,还有
大Θ表示法,那我们其实也是可以用这一套表示法 来观察我们的空间开销
那空间开销呢我们主要的是看这个算法它的辅助的空间
也就是说我需要用多少这个临时的这样的变量的空间
来完成这个算法的运算,而时间和
空间的权衡呢是在数据结构里面一个非常重要的问题
因为我们在进行问题求解的时候,我需要用一定的数据存储空间
来存放相应的数据 而我们还需要一定的时间来
执行这些算法的代码,那
因此呢时空的限制呢在很多应用里面它是有一定的要求的
那另外呢就是我们还有一些软件工程方面的一些其他的限制和要求
这都是我们要考虑的,跟算法相关的它的时空
代价,还有我们在编写和维护的效益方面的问题
在通常意义下,我们增加
这个算法的空间,也就是说我多开一些大数组 往往能够获得更快的算法的性能
而我们为了要节省空间呢,很多时候 我要在算法的设计上要做更多的一些考虑
那也就是说我们可能会增大算法的运行时间,或者是说
增加我们在编写算法方面的负担 时空的权衡呢是我们需要认真考虑的问题
我们在 对数据结构和算法进行选择的时候呢,我们首先是要考虑
我们的问题是什么,也就是说围绕着我们这个问题求解的目标
来仔细考虑我应该用什么样的数据 结构来表达这个问题的数据空间
然后呢我再考虑用什么样的方法,也就是用什么样的算法来解决这个问题
很多时候数据结构的设计它是先于 算法的设计,当然也有一些特别明显的问题
那我们可能,你可以一下子就给它演算到一个经典的什么算法
然后我再考虑用一些相应的存储方法来实现
我们还要注意呢数据结构的可扩展性,特别
是因为我们编写的算法很可能是 要跟问题规模n是相关的
那当这个n大到一定的时候,那我们的算法是不是还适应
例如我们一个线性的算法,也就是说大O(n)的算法
那在通常情况下是没有问题的,但是在搜索引擎这样的环境下
那我们要面对几百亿的这些网页,如果你还是
跟n相关的,那有可能就不能够适应我们的检索需求
那就要进行特殊的索引和检索的处理 下面给大家留几个思考
首先就是我们数据结构与算法的选择 主要的是针对问题求解而进行的
那问题求解的目标是什么?我们可以找几个例子来看一下
另外呢就是数据结构与算法选择的过程,我们是怎么 样来考虑的,我先考虑什么,再考虑什么?
我这个过程是怎样进行的?另外呢我们再回顾
一下数据结构的三个要素,也就是它的逻辑结构,它的 存储结构以及运算这三个角度
那这三个因素只要任何一个发生改变,其实我们可以说都是
不同的数据结构。谢谢大家!