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