数据结构中的算法

数据结构和算法的关系        

        谈到数据结构和算法的关系，那肯定是密不可分的。只谈数据结构当然可以，我们能在很短的时间内就把多种数据结构介绍完。但是听完后，你可能没什么感觉，不知道这些数据结构有什么用处，如果我们再把相应的算法也拿来讲一讲，你就会发现，甚至开始感慨：计算机界的前辈们真是泰裤辣，他们让很多看似难以解决的问题，变得如此美妙和神奇。

        不过话说回来，很多大学通常是把“算法”单独拎出来当做一门课去讲的。也就是说在《数据结构》课程中，就算谈到算法，也是为了帮助理解好数据结构，并不会详细谈及算法的方方面面。我们的课程也是按这样的原则来开展的。

两种算法的比较

        在18世纪生于德国小村庄的高斯，上小学的一天，课堂很乱，老师非常生气，后果自然也很严重。于是老师在放学时，就要求每个学生都计算1+2……+100的结果，谁先算出来谁先回家。天才当然不会被这样的问题难倒，高斯很快就得出了答案，是5050。老师非常惊讶，因为他自己想必也是通过1+2=3、3+3=6、6+4=10，……4950+100=5050这样算出来的，也算了很久。说不定为了怕错，还算了两三遍。可眼前的少年，为什么可以这么快得出结果？

高斯解释道：    sum = 1+   2+   3+ 4 +……+99 +100 

                      sum = 100+ 99+ 98+……    +    2 +    1

                  2*sum = 101+101+101+……   +101 + 101（共100个）      

                       所以sum = 101*100/2 = 5050

用C语言来实现：

	int sum = 0;
	int n = 100;
	sum = (1 + n) * n / 2;
	printf("%d\n", sum);

        高斯确实是天才，他用的方法相当于另一种求等差数列的算法，不仅仅可以用于1加到100，即便是加到一亿(需要更改整形变量类型为long int，否则会溢出)，也只是瞬间的事。但如果用刚才的程序，显然计算机要循环一亿次的加法运算。人脑比电脑算的快，似乎成为了现实。

算法定义

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

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

        现实世界中的问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决所有问题。甚至解决一个小问题，很优秀的算法却不一定适合它。

        指令能被人或机器等计算装置执行。它可以是计算机指令，也可以是我们平时的文字语言。为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能，这就是算法了。

算法的特性

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

        输入输出

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

        有穷性

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

        确定性

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

        可行性

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

算法的设计要求

        正确性

        算法的正确性是指算法至少应该具有输入、输入和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。

        但是算法的“正确“通常在用法上有很大区别，大体分为以下四个层次。

1、算法程序没有语法错误。

2、算法程序对于合法的输入数据能够产生满足要求的输出结果。

3、算法程序对于非法的输入数据能够满足规格说明的结果。

4、算法程序精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

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

        可读性

        算法设计的另一个目的是为了便于阅读、理解和交流。

        可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难于调试和修改。我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了都不知道写了些什么。可读性是算法（也包括实现它的代码）好坏很重要的标志。

         健壮性

        一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该等于负数等。

        健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

        时间效率高和存储量低 

        时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。储存量需求指的是算法在执行过程中需要的最大储存空间，主要指算法程序运行时所占用的内存或外部硬盘储存空间。

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