1.5算法和算法分析概念在线视频

同学们，大家好

这一节我们介绍一下算法和算法分析的概念

首先介绍一下算法的概念，前面的章节中

我们提到过算法的概念，算法是对解决问题过程的描述

它是过程性的知识，通过烤蛋糕的例子

我们对算法大概有了一个直观的感受

这里我们给出算法的一个简单定义

算法是对特定问题求解步骤的一种描述

也就是说我们把解决问题的过程

按第1步怎么做，第2步怎么做，第3步怎么做

这样的次序把解决问题的过程描述出来

如果用程序设计语言描述算法

它就表现为一个个的指令的有限序列

算法有这样几条特性，第一是有穷性

一个算法必须总是在执行有穷步之后结束

且每一步都在有穷时间内完成，简单的说

就是算法的计算必须在执行了一个有限时间之后结束

随后，能够获得我们需要的结果，不能没完没了

算法的第2个特性是确定性，它的含义是说

算法中每一条指令都必须有明确的含义

不存在二义性，并且，算法只有一个入口和一个出口

上述两点是强调，算法的过程和结果都是确定的

第3条特性是可行性。算法描述的操作，应该都是可以执行的

让万能的上帝造一块自己不能举起的石头

这样的指令上帝也执行不了

另外两个特性是算法应该有输入和输出

输入的一般是算法要处理的数据，输出呢

是根据算法的功能需求，获得的一个计算结果

下面我们介绍算法设计的要求

在我们的教材中，并没有很确切的区分算法和程序这两个概念

这两个概念实际上并不是等价的

算法用程序设计语言描述以后，一般来说肯定是一个程序

但是程序未必会是一个算法，比如包含无穷循环的程序

它是一个程序，可以在计算机上执行

但是呢，它不会结束，它并不满足算法具有有穷性这样的特征

它并不是算法

教材中没有严格区分二者，提到的算法

一般都是指程序，这里给出的算法设计的4条要求

实际的意思是说，一个好的程序，应该满足的要求

第1个要求是正确性，算法应该满足具体问题的需求

也就是说，当我们设计某个功能的时候

算法应该能够满足我们的要求，通过计算获得我们想要的结果

例如设计一个线性表插入的算法

那么它应该能满足在线性表中插入一个数据元素的要求

第2个好的算法的要求是可读性，算法应该好读

以利阅读者对程序的理解

现在的程序一般来说是大规模的程序

需要合作完成，那么合作的基础就是互相能够理解

所以，程序的可读性，对合作开发程序非常关键

程序需要进行升级的时候呢，往往需要阅读原来的程序代码

如果程序具有良好的可读性，对后续的升级非常方便

另外，可读性性对代码重用也非常重要

在软件产业中有重要意义。

好程序的第3条标准是健壮性，程序应该有容错处理

也就是说，当输入的是非法数据的时候

算法应该能对这样的非法数据，做出适当的反应

而不是产生莫名其妙的输出结果，甚至系统崩溃

在一个程序使用过程当中，因为各种原因，我们很难保证

用户输入的都是合法的数据，那么容错处理呢

就非常重要了，容错处理能给用户带来更好的使用体验

最后一条好程序的要求是效率和存储量的需求

这个比较直观，效率指的是算法执行的时间

存储的要求指的是执行过程中需要的最大存储空间

我们当然希望我们编制的程序，执行快，需要的时间少

需要的存储空间也少，这样的程序当然就是好的程序

一般来说，效率和存储量需求和问题的规模有关

比如说，对100个数据排序，对1万个数据排序

排序需要的时间和存储空间，肯定是有差异的

算法的效率和存储量要求一般可以表示为问题规模的一个函数

从上面的讨论我们可以看到，123三条是好算法定性的要求

一个程序正确性多少？可读性又是多少？健壮性又怎么样？

这些很难量化，但是，第4条是不一样的

第4条是可以定量的，程序执行的时间和它需要的空间

我们是可以给出定量的分析

那么怎样来分析算法的时空效率呢？下面我们来讨论一下

对一个算法时空效率进行分析

有两种方法，即事先分析和事后测试

事后测试指的是，通过在具体的计算机上执行程序

执行了以后，收集这个算法执行的具体时间和占有的空间

利用这些统计资料

可以对这个程序执行的时间和占用空间的情况进行分析

但是，这样的做法是有局限性的，不同的计算机

会对执行的时间和存储等产生影响

很难通过这样的统计资料说明算法的优劣

我们关注的是事先分析，事先分析想做的是

不在计算机上运行程序，而是基于算法本身的结构

求出一个算法执行时间效率和空间需求的界限函数

用这样的界限函数，作为算法时间和空间效率的度量

我们首先来讨论对算法执行时间效率的度量

不运行程序，怎么来度量一个算法的执行时间呢？

我们是以算法中基本操作重复执行的次数

作为算法执行效率的度量，这里我们所说的基本操作

可以理解为，算法当中最基本，最耗时的操作

不同的算法中基本操作可能是不同的

例如，排序算法中，基本操作是数据的比较和移动

我们可以通过比较和移动的次数来度量排序算法的执行效率

当然，排序算法中还有其他操作

但时间需求比较而言较少，可以不加考虑。

前面我们提到，基本操作重复执行的次数

一般而言也是问题规模n的某个函数

我们把它称为f（n），f（n）的含义是说

当问题规模是n的时候

算法当中基本操作执行的次数是f（n）

下面看一个例子，假设某个算法

它的f（n）等于n3方+n2方加一个常数c

也就是说，在这个算法当中

问题规模是n的时候

基本操作执行的次数是n3方+n2方加一个常数

但是，我们并不以这个f（n）作为算法执行的度量

算法执行时间的度量

我们称为t（n），t（n）称为算法的渐近时间复杂度

简称时间复杂度

t（n）是大O（f（n）），O（f（n））是对f（n）的简化

简化的方式是，第一，低阶的部分被去掉了

例子中n平方+c被去掉了；第二，如果高阶有系数的话

系数也去掉，例子中只保留了高级的部分n3方

形式上简洁多了

这样就够了吗？确实就够了

对算法执行的时间效率，我们需要的只是一个量级的估计

对问题规模小的情况，我们是不考虑的

我们更关心的是，当问题规模比较大

甚至趋于无穷的时候，算法执行时间的变化趋势

从数学知识我们知道，当n趋近无穷的时候

低价部分在总体当中所占的比例趋近于0

另外，如果高阶有系数的话

系数的不同只是一个数量的变化

系数并不能表示变化的趋势，也是可以去掉的

那么怎么针对一个具体的算法进行时间复杂度的分析呢

下一节我们会通过一些例子，来说一下

这节课就到这儿

同学们下节课再见