今天我们来复习一下数据结构与算法的关系

上一节我们了解到数据结构的定义：是相互之间存在一种或多种特定关系的数据元素的集合。

一、什么是算法？

算法定义：描述解决问题的方法。这个描述很笼统，很多人一听可能迷迷糊糊的，不明所以。我们来看看其他的定义：算法是解题方案的准确而完整地描述，是一系列解决问题的清晰指令，并且每个操作表示一个或多个指令。这个定义是被普遍认可的，在计算机中，算法就一个多个制定的一序列的指令。

一个问题或数学题有多种解决方法，要让计算机实现一个操作需要指明需要计算机执行哪些指令，每一个指令要完成什么特定功能。比如宋丹丹老师的一个小品中的一个例子：请求把大象装进冰箱要几步。这个就是一个操作，那么他们的算法(指令)就是下面的求解步骤，把大象放进冰箱需要三步:

• 1、把冰箱门打开
• 2、把大象放进去
• 3、把冰箱门关上

二、算法有哪些特性

算法具有五个特性：输入、输出、有穷性、确定性和可行性。

1、输入

算法的输入具有零个或多个输入。有人就有疑问了，零个输入怎么说，我们来举个例子，在java，刚开始学习时，一般都从在控制台打印学习开始：

System.out.print("Hello world");

在这里例子中，就没有输入的参数，我们来看看前面算法的定义：有限序列的操作，控制台打印操作是System.out.print，那么有人就有疑问了“Hello World”不就是一个输入参数吗？其他“Hello World”还真的不是输入一个参数，这个是算法另一个特征：输出

2、输出

在上面的“Hello World”例子中，我们看到了算法的输出，System.out.print，输出值是“Hello World”，算法是一定要有输出的，没有输出的算法是没有意义的，它可以是多种形态的输出方案，如上面的控制台打印输出，也可以返回一个或多个值等，没有输出的算法是没有意义的。

3、有穷性

有穷就是有限，在执行制定指令步骤后，自动结束而不会出现无限循环，并且每一个步骤在有限的时间内完成。在这里的有穷是我们一个项目中有穷非数学上的有穷。很多程序员在刚开始学习会老师都会提起过，写代码要认真点不要出现死循环，不要轻易使用循环while(true)操作，当然在实际应用有现实中的算法还是需要很长一段时间，比如数学界中圆周率到目前为主算了几十年都还没解决，未来需要多长时间才能结束，还是一个疑问，但不否定这也是一个数学界中算法。在计算中，我们实际做项目的时候，一个算法是不需要那么长的时间的，所以的项目中使用的算法，都有一个合理的，有边界的时间。你说你一个订餐系统，用户今天肚子饿了，想定个外卖，你提供的配送时间是一年，我还要等一年后才吃到这顿饭，这个就没多大意义了。

4、确定性

算法的确定性是指算法执行的每一步骤都具有确定的含义，不会出现二义性。在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果(可描述的范围内)。0就是0，1就是1。不会出现是零非零，是一非一，让人模棱两可的算法。每个步骤必须要明确的定义。

5、可行性

算法的每个指令都是可行的，也就是说每一步骤都能执行有限次数后完成指令。可行性意味着算法指令转成计算机语言上完成指定的操作后输出结果。当然目前计算机研究领域及数学领域都存在一些 不能实现的算法，那些都过于复杂，不是我们现在讨论的问题范围内，我们讨论的是在互联网业务范围内，可得到结果的算法。

三、算法设计标准

在上面我们讲算法定义的时候，聊到过一个算法有多种解决方案，比如排序就有冒泡，快排等多种排序方案。

尽管算法有多种多样，但优秀的算法还是不少的，掌握好的算法，对我们解决问题是非常有帮助的，那什么样的算法才是好的算法，算法设计标准是什么呐：

1、正确性

优秀的算法最起码的要求是正确性，如果连正确性都达不到，那这个算法连对不对都谈不上，算法正确性是指算法在规定时间内，按照规定要求的输入，输出和加工处理无歧义，能准确反应问题的需求，能得到问题的正确答案。

算法的“正确”通常会存在一些歧义，特别是在大家对答案没有标准的认知时，但大体上可以分为四个要求。

• 语法语法正确，没有出现错误的语法，导致算法无法运行
• 对于合法的输入参数能够输出符合要求的输出结果
• 对于非法的输入参数能够符合要求的输出说明结果
• 对于具有挑战性的测试数据也能够输出满足要求的输出结果

对于这四个要求，第一个要求是最容易的，如果一个算法连最基本的语法是否正确都做不到，那谈不上是优秀的算法了，其次是第二，第三，第四条。特别是第四条，我们几乎是无法全部验证所有的测试结果，这点只能交给数学方法来证明了，证明一个算法符合这四个要求，代价是很高的，所以我们有时会前三个作为验证一个算法是否正确的标准要求，那么一个正确的算法是否应该符合所有人来理解呐，这就涉及到算法的第二个标准：可读性

2、可读性

一个好的算法是便于阅读、理解和交流。假如一个算法晦涩难懂，那肯定不是一个便于曹啧啧啧的优秀算法。可读性高的算法，人们容易理解，大家都愿意去接受它。

我曾经带过几个团队，很少有程序员愿意写注释，写文档是程序员最排斥的工作，那问题就来，假如不写注释，那您的代码又难于阅读，一个类上千行，一个方案多达几百行，更有人一个复杂业务一个方法全部搞定，一千多行代码，十几个ifelse，看起来头都疼了。

我们写代码的目的是为了让计算机执行，但还有一个目的是便于他人阅读，因为您不可能在一个岗位干很久，这个代码也不可能一直是您来维护，那你的代码就必须让对接你的人便于阅读，自己将来也能看得懂你自己代码，想起网络一个段子，一个码农看到一个代码，大骂一顿：哇靠，这谁写的代码，一坨屎，仔细看一遍：哇靠，原来我自己写的。如果可读性不好的代码，时间长了，你自己都不知道写了是什么，先阶段，可读性是算法好坏的一个重要标注。

3、健壮性

对于上面的讨论算法正确性的四个要求时，我们聊过第三个要求“对于非法的输入参数能够符合要求的输出说明结果”，我们大家都知道，对于一个问题，大家理解都不一定，对于问题提出的前提，大家理解也不一定，前提多了，很少有人能记得住全部前提，这里所说的前提与算法的输入有一定的关系，一个在跑的算法，有些用户或客户会经验会输入错误的参数，比如验证码，这时候我们的算法就得对于这些输出做出合理的提示，这就是这一节我们要讲的，一个好的算法需要具备健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

4、时间效率高和存储量低

最后还有一点，那就是一个优秀的算法需要具备时间效率和存储量低的特点。

假如一个简单业务需求，一个算法需要耗时十几天二十天才是执行完，这显然不是很合理，我们当然会选择执行时间相对比较短的算法，存储量是指算法执行过程中需要占用的存储空间(这里需要说明内存、硬盘存储、CPU都要考虑)，因为我们实际业务中，不可能只用到一个算法，需要多个算法同时运行，所以就需要存储空间小，执行时间段的算法，我们设计时就要考虑这两个问题：尽量满足时间效率高和存储量低的需求

综上，一个优秀的算法应该具备：正确性、可读性、健壮性、高效率和低存储量的特征

数据结构与算法的关系(上):算法的特征