数据结构 - 算法的定义

两种算法的比较

给一个编程问题，求 1 到 100 的和，用编程实现。 相信我们很快就能想到第一种：

int sum = 0, count = 100;
for (int i = 1; i <= count; i++) {
    sum += i;
}
printf("%d", sum); // 5050

这就是一种算法，通过这种方式的却能得到最终结果，但是由于涉及到循环，当数据量庞大时，效率可想而知了。

再思考思考，能不能有更优的算法呢？找找其中的规律，可以发现 1 + 100 = 101，2 + 99 = 101，依次类推。可以得到另一种解决方式：

int count = 100;
int sum = (count + 1) * count / 2;
printf("%d", sum); // 5050

这就是一个简单的求等差数列算法。 通过这个例子，可以发现算法的美妙之处了。 如果你在同一个类似程序中发现有的运行快，有的运行慢，其中就有可能是快的一方运用到了算法喔！

算法定义

算法（Algorithm）是描述解决问题的方法。如今普遍认可的对算法的定义是：

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

算法的特性

算法具有几个基本特性，分别如下。

输入输出

算法具有零个或多个输入，并且至少有一个或多个输出。

尽管对于大多数算法来说，输入参数都是非常有必要的。但是对于个别情况，如打印 “Hello World！” 这样的代码是不需要参数的。 但是，算法是必须要有输出的。输出的形式可以是打印输出，也可以是返回一个或多个值。

有穷性

算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。

写的代码死循环了，那么这就不满足有穷性。当然这里的有穷性并不是指纯数学意义的，而是在实际应用中合理的、可以接受的 “有边界”。
要是写一个算法，运行个几十年后才有结果，这在数学意义上来说得确是满足有穷性了，但是意义也就不大了。

确定性

算法的每一个步骤都具有确定的含义，不会出现二义性。

算法在一定的条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。

可行性

算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

可行性意味着算法可以转换为程序运行，并得到正确的结果。

算法设计的要求

通过上面那个例子我们就能够看到，算法并不唯一。同一个问题，可能会有多个算法可以解决。 那么对于算法而言，也存在与好的算法和坏的算法。那么什么才叫好的算法呢？

首先第一个，也是最基本的一个。好的算法，必须是正确的。

正确性

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

但是算法的 “正确” 在用法上有很大的差别，大体分为如下四个层次：

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

对于这四层含义，我们通常以层次 3 作为一个算法是否正确的标准。

可读性

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

也就是说，一个好的算法，应该不仅自己能够看懂，别人也能够看懂。
过分极致的追求最少的代码，往往会降低代码的可阅读性，这往往并不可取。

健壮性

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

一个好的算法还应该能够对输如不合法的数据进行合适的处理，比如说，输入的年龄不应该为负数。

时间效率高和存储量低

最后，好的算法还应该具备时间效率高和存储量低的特点。

• 时间效率指的是算法的执行时间。
• 存储量需求指的是算法在执行过程中需要最大的存储空间，越低越好。主要指算法程序运行时所占用的内存或外部存储空间。

我们在设计算法时，应该尽量去做到这一点。综上，一个好的算法应该具备：正确性、可读性、健壮性、时间效率高和存储量低的特征。

算法效率的度量方法

算法的效率大都指的是算法的执行时间。那么我们如何去计算算法所执行的时间呢？

事后统计方法

这种方法主要是通过设计好的测试程序和数据，利用计算机对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

但是这种方法会有很大的弊端：

• 需要花费大量时间和精力来根据算法编写测试程序或数据。
• 依赖的计算机环境并不一致。
• 算法的测试数据设计困难。

事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算。

计算机前辈们，为了对算法的评判更科学，研究出了一套事前分析估算的方法来计算算法的效率。 经过分析，我们发现，一个用高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素：

1. 算法采用的策略、方法。
2. 编译产生的代码质量。
3. 问题的输入规模。
4. 机器执行指令的速度。

第一条是算法好坏的根本，第二条由软件来支持，第四条要看机器的硬件性能。也就是说，抛开这些与自身和软件、硬件因素，剩下的就只有问题的输入规模了。

问题的输入规模就是指的输入量的多少。

我们在分析一个算法的运行时间时，重要的是要把操作的数量和输入规模相关联起来。

来看看开头的第一个例子，输入规模就指的就是 count：

int sum = 0, count = 100;
for (int i = 1; i <= count; i++) {
    sum += i;// 一次计算操作（操作数量随输入规模）
}
System.out.println(sum);

可以看到，输入规模越大，操作数量也越多。 1 + 2 + 3 + n… 需要一段代码运行 n 次，那么这个问题的输入规模使得操作数量是 f（n）= n。

再来看看第二个例子：

int count = 100;
int sum = (count + 1) * count / 2;// 执行一次（操作数量）
System.out.println(sum);

在该例子中，无论 count 为多少，其操作数量依然为 1。即 f（n）= 1。算法的优劣，由此可见。

我们并不关心编写程序所用的语言是什么，也不关心这些程序将跑在什么样的计算机中，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作。

最终，在分析程序的运行时间时，最重要的是把程序看成是独立与程序设计语言的算法或一系列步骤。

参考

《大话数据结构》