《数据结构》第五部分：算法概述与时间复杂度大O法精讲

越狱.jpg

引言

Niklaus Wirth曾提出了一个程序公式：程序=数据结构+算法。

算法是数据结构的灵魂，这句话一点也不为过。一个数据结构设计的再好，如果没有算法，如同失去了灵魂的人，它的存在就毫无意义。将算法和数据结构结合起来，才能对数据结构进行各种运算操作。

既然算法如此重要，我们接下来就学习一下什么是算法。

算法是什么

算法（algorithm）是解决特定问题的步骤描述，简单的说，算法就是描述解决问题步骤的方法。

例如，新学期开学，学生从家到学校的交通方式这个问题就有很多种解决方案：

有的学生乘坐火车；

有的学生乘坐汽车；

有的学生乘坐飞机；

距离学校很近的学生可能骑自行车或者做公共汽车；

有的学生可能步行就到学校了。。。

这些方案中的每一种就是一种算法，这么多解决方法就是这么多种算法。

在计算机中，算法也是对某一个问题的求解方法，只是他的表现形式是计算机指令的有序序列，执行这些指令就能够解决特定的问题。

例如，在高级程序设计语言中（C、C++、Java），常用的排序算法（冒泡排序，选择排序等）都是用计算机指令编写算法，从而解决排序问题。

在程序设计中，算法有3种较为常用的表示方法：

伪代码法

N-S结构化流程图法

流程图法

其中用的最多的是最后一种：流程图法

流程图法

流程图是描述问题处理步骤的一种常用的图形工具，他由一些图框和流程线组成。

使用流程图描述处理问题的步骤，形象直观，便于阅读。

画流程图时必须按照功能选用相应的流程图符号，常用的流程图符号如下展示：

流程图符号.png

这里说明一下

 * 起止框用于表示流程的开始或者结束，我们看到是一个圆边矩形 * 输入输出框用平行四边形表示，在平行四边形内可以写明输入或者输出的内容 * 判断框用菱形来表示，它的作用是对条件进行判断，根据条件的是否成立来决定如何执行后续的操作 * 处理框用矩形表示，它代表程序中的处理功能，如算术运算或者赋值等 * 流程线用单向箭头或者直线表示，可以连接不同位置的图框。流程线的标准流向是从左到右，从上到下，可以用直线表示，非标准流向的流程线应使用箭头指明方向。 * 连接点用圆形表示，用于流程图的延续。

ok,根据上边的解释，大家应该对流程图有了一定的认识了吧，下方以一个选择排序的算法流程图为例，简单学习一下流程图的使用，如下图：

选择排序流程图.png

解释一下：

假设一个数组要从小到大排序，结合流程图来分析选择排序的过程：

第一步：在数组中选择出最小的值，将它与角标0的元素进行交换，即放在开头第一位

第二步：除角标为0的元素外，从剩下的待排序元素中选择出最小的元素，将它与角标为1的元素进行互换，即放在第二位

第三步：以此类推，直到完成最后两个元素的排序交换，至此，完成了整个升序排列。

这样，根据流程图来编写算法的指令代码，就会变的很清晰。大家在以后设计算法时，可以先根据设计思路画出算法的流程图，其次分析其可行性，最后再完成代码，这样应该思路会更加清晰，代码的bug也会少很多。

算法的特性

一个好的算法，尤其是一个成熟的算法，应该具备以下5个特性：

（1）确定性。算法的每一步都有明确的含义，不会出现二义性。即在相同的条件下，只有一条执行路径，相同的输入只会产生相同的输出结果。

（2）可行性。算法的每一步都是可执行的，通过执行有限次操作来完成其功能。

（3）又穷性。一个算法必须在执行又穷步骤之后结束，且每一步都可以在又穷时间内完成。这里的有穷概念不是数学意义上的，而是指在实际应用中可以接受的，合理的时间和步骤。

（4）输入。算法具有零个或多个输入。有些输入量需要在算法执行过程中输入；有的算法表面上没有输入，但实际上输入量已经被嵌入到了算法中了。

（5）输出。算法至少具有一个或多个输出。“输出”是一组与“输入”具有对应关系的量值，是算法进行信息加工后的到的结果，而这种对应关系即算法的功能。

ok，一个好的算法需要具备这5个条件。那么在设计算法时，怎样才能设计出好的算法呢？这就需要在设计算法时有明确的目标。想要设计出一个好的算法，需要从以下4个方面来考虑：

（1）正确性。算法能够正确的执行，实现预定的功能。这是算法最重要也是最基本的要求，它包含程序没有语法错误；对于合法的输入能够产生满足要求的输出结果；甚至对于非法的测试数据都能有满足要求的输出结果。一个好的算法必定经得住千锤百炼的测试。

（2）可读性。算法应该易于理解，也就是可读性好，这就要求算法的逻辑必须是清晰、简单和结构化的。可读性好有助于程序员理解算法，晦涩难懂的算法往往会隐藏错误且不易于被发现，难于测试和修改。

（3）健壮性。要求算法具有高容错性，即提供异常处理，能够对不合理的数据进行校验检查，不经常出异常中断或者死机现象。

（4）高效率和低存储。算法的效率通常指的是算法的执行时间，对于同一个问题的多种算法，执行时间段的其效率就高。存储量指得是算法在执行过程中所需的最大存储空间，包括所用到的内存和外存。设计算法时应该考虑到执行效率和存储需求，设计出一个“性价比”较高的算法。

ok,要设计出一个好的算法，就要综合考虑其正确性、可读性、健壮性，还要考虑其执行效率和存储量需求。

算法的复杂度

分析一个算法主要看这个算法的执行需要多少机器资源。在各种机器资源中，时间和控件是两个主要的方面。因此，在进行算法分析时，人们最关心的就是运行算法所要花费的时间和算法汇总使用的各种数据所占用的空间资源。

算法所花费的时间通常称为时间复杂度，使用的空间资源称为空间复杂度。

1、时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，然后分析T(n)随n的变化。

T(n)=O(f(n))

这种用大写的O来标记算法的时间复杂度，称为大O（Order的缩写）标记法。一般随着n的增长，T(n)也会随着增长，其中T(n)增长最慢者就是时间性能最优的算法。

在计算时间复杂度的时候，根据T(n)与n的最高阶数关系，我们给这些算法的复杂进行了归类，归类情况如下表所示

算法复杂度关系.png

除了上面的这几种关系，当然还会有其他阶数关系，这里只是列出了几个常见的关系。

算法的执行次数可能会与规模n呈现出这些关系，那么这些关系又是如何推导出来的呢？下面给出大O阶的推导方法：

（1）用常数1取代运行中所有的加法常数

（2）在修改后的运行次数函数中，只保留最高阶项

（3）如果最高阶项存在，且不是1，则除去其常系数，得到的结果就是大O阶。

举几个例子

接下来通过分析几段程序的执行过程来推导出其时间复杂度

例1：

 int a=100; //执行一次 int b=200; //执行一次 int sum=a+b; //执行一次 printf(“%d\n”,sum); //执行一次

上面程序段有4行代码，每一行代码执行一次，加起来一共执行了4次，f(n)=4,即T(n)=O(4)。

根据推导方法中的第一条，将常数项用1代替。在保留其最高阶项时，我们发现并没有最高阶项，因此该算法的时间复杂度是O(1),为常数阶。

例2：

 void function(){ int i,sum=0; //执行1次 for(i=0;i<=100;i++){ sum+=i； //执行n次 } printf("%d\n",sum); //执行1次 }

该程序段的执行次数为1+n+1，即f(n)=n+2。然后根据规则，我们把数项用1代替，且只保留到最高阶，则得出T(n)=O(n),因此这个算法的时间复杂度为O(n)，为线性阶。

例3：

 void func(){ int i=1; do { i*=2; } while(i<n); }

在这个程序段中，当i<n时，程序循环结束。如果循环了f(n)次，则就有这样的情况

2f(n)=n

那么我们计算一下f(n)为多少

f(n)=log2n

即我们得知这个算法的时间负责度为

T(n)=O(log2n)。

我们根据规则，将常系数消除，爆了最高阶，最后得出

T(n)=O(logn)，为对数阶。

用大O阶来推导算法的复杂度并不难，我们在以后学习中设计算法，多数就可以用这种方法来估测算法的优劣。当然我们以后谈算法的复杂度时，也是以大O阶来判定的。

2、空间复杂度

空间复杂度是对一个算法在运行过程中所占用的存储空间的大小的度量，一般也作为问题规模n的函数，以数量级形式给出，格式如下：

S(n)=O(f(n))

一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。在对算法进行分析时，只考虑辅助变量所占空间。

若所需辅助空间相对于输入数据量来说是常数，则称此算法为原地工作。

若所用空间量依赖于特定的输入，则除了有特殊说明之外，均按最坏情况考虑。

有时候，在写代码时可以

用空间来换取时间

例如：

写一个算法来判断某年是否是闰年，这样每输入一个年份都要去调用算法判断一下，在时间上就有点复杂了。为了提高效率，可以用空间来换取时间，即建立一个大小合适的数据，编号从0到n，如果是闰年，则存入数据1，否则存入数据0。这样只要通过判断年份编号上存储的是0还是1就知道该年份是否是闰年了。

用空间换取时间可以将运算最小化，但是到底需不需要这样做，还得结合实际情况来定。

一般情况下，都是用时间复杂度来度量算法，当不加限定地使用“复杂度”这一术语时，都是指时间复杂度。

总结

计算机软件的最终成果都是以程序的形式体现的，一个程序应该包含以下两方面的内容：

（1）对数据的描述。在程序中指定用到哪些数据以及这些数据的类型和数据的组织形式，也就是数据结构。

（2）对数据操作的描述。即操作步骤，也就是算法。

数据结构算法的基础，算法是数据结构的灵魂。数据结构设计和算法分析的目的是设计更好的程序。

程序的本质是为要处理的问题选择好的数据结构，同时在此结构上施加一种好的算法。

数据存储结构会影响算法的好坏，因此在选择存储结构时，也要考虑其对算法的影响。例如，如果存储结构的存储能力较强，则可以存储较多的信息，算法将会好设计一些。反之，对于过于简单的数据结构，基于该结构的算法设计可能会比较复杂一些。

总之一句话：

选择合适的数据结构和算法，会让我们事半功倍~