算法基础_数据结构与算法教程

1. 算法的特性

1) 输入输出

算法具有零个或者多个输入，同时，算法具有至少一个的输出。

对于在屏幕上打印”Hello World”一样，你可以不需要有任何的输入，直接输出得到结果即可，而对于一个没有输出的算法，没有任何意义。

2) 确定性

算法的每一步都具有确定的含义，无二义性。任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

请注意，如果算法的目的是产生一个随机数字，每一次运行产生了不同的结果，看上去好像违反了算法确定性原则，但计算机产生随机数亦是使用一种（或多种）算法解决，以线性同余产生随机数为例，其利用了CPU时间的不同产生的不同的结果，当CPU的时间完全一样的时候依旧会产生相同结果，只不过人类无法察觉到如此精确的时间区别。

3)有穷性

一个算法总是需要（输入合法的情况下）在有限的步骤结束，即每个算法需要在有穷的时间内完成。

这是算法与程序的最主要的区别，程序可以无限制循环的执行下去。对于此，你可以理解为一个算法必须要有一个”边界“，即使一个算法需要计算机连续运算50年，但依旧是有穷的，只不过这个算法意义已经不是很大了。

4)可行性

一个算法是可以被执行的，即算法中的每个操作都可以通过已经实现的基本运算执行有限的次数完成。

尽管在目前计算机解存在着没有实现成功的极为复杂的算法，但是并不能说的上是无法实现，只不过是受到现在的工具和人类的大脑限制了，这属于理论研究的范围。

2. 算法设计要求

1) 正确性

正确性（Correctness）指的是该算法能够满足预先指定的功能与性能的需求，即能够得到正确答案。

其大致可以分为以下四点：

a)该算法中不含任何语法错误。

b)程序对于几组输入数据能够得到满足需求的结果。

c)程序对于非法的输入也能够得到满足需求说明的结果（如抛出异常）。

d)程序对于精心挑选的严苛数据依旧能够产生满足需求的结果。

2)健壮性

健壮性（Robustness）指的是当输入数据不合法时，算法也能做出相关的处理，而不是产生不可预计的效果。

3)可读性

可读性（Readability）指的是算法是可以阅读，理解和交流的。

4)耗时低，占用空间少

运行时间（Running time）与占用空间（Storage space）概念，在设计算法时，我们总是希望能够更少的使用时间和空间达成我们的目标。

我们算法与数据结构的研究的重点就是为了让程序运行块，占用空间低。