数据结构与算法的深度解析

发表时间: 2019-07-19 19:54

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

有不少书叫“数据结构与算法分析”这样的名字，那么到底是只讲数据结构呢，还是和算法一起讲？他们之间有什么关系呢？干嘛要放在一起？

我们可以从分析问题的角度去理清数据结构和算法之间的关系。通常，每个问题的解决都经过以下两个步骤：

1.分析问题，从问题中提取出有价值的数据，将其存储；

2.对存储的数据进行处理，最终得出问题的答案；

数据结构负责解决第一个问题，即数据的存储问题。通过前面的学习我们知道，针对数据不同的逻辑结构和物理结构，可以选出最优的数据存储结构来存储数据。

而剩下的第二个问题，属于算法的职责范围。算法，从表面意思来理解，即解决问题的方法。我们知道，评价一个算法的好坏，取决于在解决相同问题的前提下，哪种算法的效率最高，而这里的效率指的就是处理数据、分析数据的能力。

两种算法的比较

大家已经学过至少一门计算机语言，不管学的是哪一种，学得好不好，好歹可以写一些小程序了。现在要求写一个求 1+2+3+......+100结果的程序，应该怎么写呢？

大多数人会马上写出下面的代码:

这是最简单的计算机程序之一，它就是一种算法，我不去解释这段代码的含义了。问题在于，你的第一直觉是这样写的，但这样是不是真的很好？是不是最高效？

此时，不得不把伟大数学家高斯的童年故事拿来说一遍，也许你们早已听过，但不妨在感受一下，天才是如何展示天分和才华的。

18世纪生于德国小村庄的高斯，上小学的一天，课堂很乱，老师很生气，后果很严重。于是老师在放学时，就要求每个学生都计算 1+2+3+......100 的结果，谁先算出来谁先回家。

天才当然不会被这样的问题难倒，高斯很快就得出了答案，是 5050，老师非常惊讶，因为他自己想必也是通过 1+2,3+3,6+4，.....,这样算出来的，也算了很久很久。说不定为了怕错，还算了两三遍。可眼前这个少年，为何可以这么快得出结果？

高斯解释道：

用程序实现如下:

很显然，用这种方法就算计算一千，一万，甚至一亿的加法运算，也就是一瞬间的。人脑比电脑算得快，似乎成为了现实。

算法的特性

输入输出：算法具有零个或多个输入，至少有一个或多个输出
有穷性：指的是算法在执行优先的步骤之后，自动结束而不会出现无限循环，并且每个步骤在可以接收的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。当然有穷并不是纯数学意义的，而是在实际应用中合理的。可以接受的边界。假如写一个算法，需要算上二十年，一定会结束，在数学上是有穷了，可以媳妇都熬成婆了，算法的意义也不大了。
确定性：算法的每一步骤都具有明确的含义，不会出现二义性
可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成

算法设计的要求

设计算法应尽量满足时间效率高和存储量低的需求

在生活中，人们都希望花最少的钱，用最短的时间，办最大的事情，算法也是一样的思想，最好用最少的存储空间，花最少的时间，办成同样的事就是好的算法。