1.3.3　比较两种算法的优劣

在计算机中，计算某个数值会有多种算法，这时需要比较这些算法的优劣。运筹学是和计算机科学密不可分的一门学科，可以帮助我们找到更优的算法。可以用下面的例子来体会运筹学在算法中的作用。

在数学中，我们都知道一个很著名的数列，即“斐波那契数列”，是指前两项相加得到第三项的数列。例如：1+1=2，1+2=3，2+3=5……斐波那契数列在许多方面都有应用。例如物理、生物、交通规划等方面。黄金分割也是依据斐波那契数列来的，被广泛应用于艺术和工业设计等领域。

现在需要计算斐波那契数列中各项的值。如果仅仅已知斐波那契数列的第1项和第2项都是1，如何来求斐波那契数列中第5项的值呢？在计算机中，可以用下面两种算法进行计算：

算法一　每一项都分开计算

现在来求第5项的值，先分别求出斐波那契数列第3项和第4项的值，即可知道第5项的值，如图1-1所示。

首先，计算第3项的值。因为前两项都是1，开始进行计算，第一次计算得到第3项的值是2，也就是说，一共只需计算1次。

其次，计算第4项的值。因为前两项都是1，开始进行计算，第一次计算得到第3项的值是2，第二次计算得到第4项的值是3，一共需要2次计算。

最后，再通过一次计算，也就是将第3项的值和第4项的值相加，得到第5项的值是5，整个过程共需要4次计算，因为1+2+1=4。

图1-1　算法一：每一项都分开计算

算法二　不分开计算

算法一的计算思路中包含了大量的重复性工作。其中，计算第3项的值重复了两次。这其实是不必要的。因此，无须将第3项和第4项的值分开来计算。要求第5项的值，只需知道第3项和第4项的值。现在，要求第4项的值就需要知道第3项的值和第2项的值（已知），而求第3项的值只需要知道第1项的值（已知）和第2项的值（已知）即可。

因此，不妨先经过第一次计算得到第3项的值为2，第二次计算得到第4项的值为3，第三次计算得到第5次的值为5，一共只需3次计算即可，如图1-2所示。

图1-2　算法二：不分开计算

比较上面两种计算斐波那契数列的方法，可以发现第二种算法帮助我们提高了计算效率，免去了一些重复性的工作。其实，第二种方法就是运筹学中的动态规划，它可以帮助我们找到效率较高的解决方案。