数据结构与算法

  虽然这门课程叫数据结构，但很多时候都会讲到算法，以及他们之间的关系。市场上也  有不少书叫“数据结构与算法分析”这样的名字。 有人可能就要问了，那你到底是只讲数据结构呢，还是和算法一起讲?它们之间是什么关系呢?干吗要放在一起?   这问题怎么回答。打个比方吧，今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院，抬头一看——《梁山伯》18:00开演。嗯，怎么会是这样?一问才知，今天饰演祝英台的演员生病，所以梁山伯唱独角戏。真是搞笑了，这还有什么看头。于是你们打算去看爱情电影。到了电影院，一看海报—-《罗密欧》，是不是名字写错了，问了才知，原来饰演朱丽叶的演员因为嫌弃演出费用太低，中途退演了。制片方考虑到已经开拍，于是就把电影名字定为《罗密欧》，主要讲男主角的心路旅程。哎，这电影还怎么看啊?   事实上,数据结构和算法也是类似的关系。只谈数据结构，当然是可以，我们可以在很短的时间就把几种重要的数据结构介绍完。听完后，很可能你没什么感觉，不知道这些数据结构有何用处。但如果我们再把相应的算法也拿来讲一讲，你就会发现，甚至开始感慨:哦，计算机界的前辈们,的确是一些很牛很牛的人，他们使得很多看似很难解决或者没法解决的问题,变得如此美妙和神奇。   不过话说回来，现在好多大学里,通常都是把“算法”分出一门课单独讲的，也就是说，在《数据结构》课程中，就算谈到算法，也是为了帮助理解好数据结构，并不会详细谈及算法的方方面面。

算法的定义

  什么是算法呢?算法是描述解决问题的方法。算法（Algorithm）这个单词最早出现在波斯数学家阿勒·花刺子密在公元825年(相当于我们中国的唐朝时期）所写的《印度数字算术》中。如今普遍认可的对算法的定义是:

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

算法的特性

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

输入输出

  输入和输出特性比较容易理解，算法具有零个或多个输入。尽管对于绝大多数算法来说，输入参数都是必要的，但对于个别情况，如打印“hello world!”这样的代码，不需要任何输入参数，因此算法的输入可以是零个。算法至少有一个或多个输出，算法是一定需要输出的，不需要输出，你用这个算法干吗?输出的形式可以是打印输出，也可以是返回一个或多个值等。

有穷性

  有穷性:指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以接受的“有边界”。你说你写一个算法，计算机需要算上个二十年，一定会结束，它在数学意义上是有穷了,可是媳妇都熬成婆了,算法的意义也不就大了。

确定性

  确定性:算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。

可行性

  可行性:算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法，不是说理论上不能实现,而是因为过于复杂，我们当前的编程方法、工具和大脑限制了这个工作，不过这都是理论研究领域的问题，不属于我们现在要考虑的范围。

算法设计的要求

  刚才我们谈到了，算法不是唯一的。也就是说，同一个问题，可以有多种解决问题的算法。这可能让那些常年只做有标准答案题目的同学失望了，他们多么希望存在标准答案，只有一个是正确的，把它背下来，需要的时候套用就可以了。不过话说回来，尽管算法不唯一，相对好的算法还是存在的。掌握好的算法，对我们解决问题很有帮助，否则前人的智慧我们不能利用，就都得自己从头研究了。那么什么才叫好的算法呢?   嗯，没错，有同学说，好的算法，起码要是正确的，连正确都谈不上，还谈什么别的要求?

正确性

  正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。   但是算法的“正确”通常在用法上有很大的差别,大体分为以下四个层次。

1. 算法程序没有语法错误。
2. 算法程序对于合法的输入数据能够产生满足要求的输出结果。
3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

  对于这四层含义，层次1要求最低，但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱，不能算是生活幸福一样。而层次4是最困难的，我们几乎不可能逐一验证所有的输入都得到正确的结果。   因此算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次3作为一个算法是否正确的标准。   好算法还有什么特征呢?

可读性

可读性:算法设计的另一目的是为了便于阅读、理解和交流。   可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现,并且难于调试和修改。   我在很久以前曾经看到过一个网友写的代码，他号称这程序是“用史上最少代码实现俄罗斯方块”。因为我自己也写过类似的小游戏程序，所以想研究一下他是如何写的。由于他追求的是“最少代码”这样的极致，使得他的代码真的不好理解。也许除了计算机和他自己，绝大多数人是看不懂他的代码的。   我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读,让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了些什么。可读性是算法（也包括实现它的代码）好坏很重要的标志。

健壮性

  一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。   健壮性:当输入数据不合法时,算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

时间效率高和存储量低

  最后，好的算法还应该具备时间效率高和存储量低的特点。   时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。在生活中，人们都希望花最少的钱，用最短的时间，办最大的事，算法也是一样的思想，最好用最少的存储空间，花最少的时间,办成同样的事就是好的算法。

算法时间复杂度

算法时间复杂度定义

  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n）随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

  这样用大写O[)来体现算法时间复杂度的记法,我们称之为大О记法。   一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。   显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为o(n),o(1)，0(n2)。我们分别给它们取了非官方的名称，O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶，当然，还有其他的一些阶,我们之后会介绍。

那么如何分析一个算法的时间复杂度呢?即如何推导大О阶呢?

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

常见的时间复杂度

在这里插入图片描述

常用的时间复杂度所耗费的时间从小到大依次是: O(1)<O(logn)<O(n)< O(nlogn)< O(n2)<O(n3)<O(2")<O(n)<O(n")

算法空间复杂度

  我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点)，然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。   这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:s(n)=o(f(n))，其中,n为问题的规模，f(n)为语句关于n所占存储空间的函数。   一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。   通常，我们都使用“时间复杂度”来指运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。

做了这么一段时间的编程工作，个人觉得，如果一个程序员弄不明白算法时间复杂度，这是一件很可悲的事情，这意味着这个人不清楚自己写的代码效率如何，是不是可以通过优化让计算机更加快速高效。

希望大家在今后的学习中，好好利用算法分析的工具,改进自己的代码，让计算机轻松一点，这样你就更加胜人一筹。