Question

2.2.什么是算法分析

一些普遍的现象是，刚接触计算机科学的学生会将自己的程序和其他人的相比较。你可能还注意到，这些计算机程序看起来很相似，尤其是简单的程序。经常出现一个有趣的问题。当两个程序解决同样的问题，但看起来不同，哪一个更好呢？

为了回答这个问题，我们需要记住，程序和程序代表的底层算法之间有一个重要的区别。正如我们在第 1 章中所说，一种算法是一个通用的，一步一步解决某种问题的指令列表。它是用于解决一种问题的任何实例的方法，给定特定输入，产生期望的结果。另一方面，程序是使用某种编程语言编码的算法。根据程序员和他们所使用的编程语言的不同，可能存在描述相同算法的许多不同的程序。

要进一步探讨这种差异，请参考 ActiveCode 1 中显示的函数。这个函数解决了一个我们熟悉的问题，计算前 n 个整数的和。该算法使用初始化值为 0 的累加器（accumulator）变量。然后迭代 n 个整数，将每个依次添加到累加器。

def sumOfN(n):
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i

    return theSum

print(sumOfN(10))

ActiveCode 1

现在看看 ActiveCode 2 中的函数。乍一看，它可能很奇怪，但进一步的观察，你可以看到这个函数本质上和前一个函数在做同样的事情。不直观的原因在于编码习惯不好。我们没有使用良好的标识符（identifier）名称来提升可读性，我们在迭代步骤中使用了一个额外的赋值语句，这并不是真正必要的。

def foo(tom):
    fred = 0
    for bill in range(1,tom+1):
        barney = bill
        fred = fred + barney

    return fred

print(foo(10))

ActiveCode 2

先前我们提出一个问题是哪个函数更好，答案取决于你的标准。如果你关注可读性，函数 sumOfN 肯定比 foo 好。事实上，你可能已经在介绍编程的课程中看到过很多例子，他们的目标之一就是帮助你编写易于阅读和理解的程序。然而，在本课程中，我们对算法本身的表示更感兴趣（当然我们希望你继续努力编写可读的，易于理解的代码）。

算法分析是基于每种算法使用的计算资源量来比较算法。我们比较两个算法，说一个比另一个算法好的原因在于它在使用资源方面更有效率，或者仅仅使用的资源更少。从这个角度来看，上面两个函数看起来很相似。它们都使用基本相同的算法来解决求和问题。

在这点上，重要的是要更多地考虑我们真正意义上的计算资源。有两种方法，一种是考虑算法解决问题所需的空间或者内存。解决方案所需的空间通常由问题本身决定。但是，有时候有的算法会有一些特殊的空间需求，这种情况下我们需要非常仔细地解释这些变动。

作为空间需求的一种替代方法，我们可以基于算法执行所需的时间来分析和比较算法。这种测量方式有时被称为算法的“执行时间”或“运行时间”。我们可以通过基准分析（benchmark analysis）来测量函数 SumOfN 的执行时间。这意味着我们将记录程序计算出结果所需的实际时间。在 Python 中，我们可以通过记录相对于系统的开始时间和结束时间来对函数进行基准测试。在 time 模块中有一个 time 函数，它可以在任意被调用的地方返回系统时钟的当前时间（以秒为单位）。通过在开始和结束的时候分别调用两次 time 函数，然后计算差异，就可以得到一个函数执行花费的精确秒数（大多数情况下是这样）。

Listing 1

import time

def sumOfN2(n):
    start = time.time()

    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i

    end = time.time()

    return theSum, end-start

Listing 1 嵌入了时间函数，函数返回一个包含了执行结果和执行消耗时间的元组（tuple）。如果我们执行这个函数 5 次，每次计算前 10,000 个整数的和，将得到如下结果：

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds

我们发现时间是相当一致的，执行这段代码平均需要0.0019秒。如果我们运行计算前 100,000 个整数的和的函数呢？

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds
>>>

再次的，尽管时间更长，但每次运行所需的时间也是非常一致的，平均大约多10倍。 对于 n 等于 1,000,000，我们得到：

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds
>>>

在这种情况下，平均值也大约是前一次的10倍。现在考虑 ActiveCode 3，它显示了求解求和问题的不同方法。函数 sumOfN3 利用封闭方程而不是迭代来计算前n个整数的和。

$\sum_{i=1}^n i=\frac{(n)(n+1)}{2}$​i=1​∑​n​​i=​2​​(n)(n+1)​​

def sumOfN3(n):
   return (n*(n+1))/2

print(sumOfN3(10))

ActiveCode 3

如果我们对 sumOfN3 做同样的基准测试，使用 5 个不同的 n (10,000, 100,000, 1,000,000, 10,000,000 和 100,000,000), 我们得到如下结果

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

在这个输出中有两件事需要重点关注，首先上面记录的执行时间比之前任何例子都短，另外他们的执行时间和 n 无关，看起来 sumOfN3 几乎不受 n 的影响。

但是这个基准测试能告诉我们什么？我们可以很直观地看到使用了迭代的解决方案需要做更多的工作，因为一些程序步骤被重复执行。这可能是它需要更长时间的原因。此外，迭代方案执行所需时间随着 n 递增。另外还有个问题，如果我们在不同计算机上或者使用不用的编程语言运行这个函数，我们也可能得到不同的结果。如果使用老旧的计算机，可能需要更长时间才能执行完 sumOfN3。

我们需要一个更好的方法来描述这些算法的执行时间。基准测试计算的是程序执行的实际时间。它并不真正地提供给我们一个有用的度量（measurement），因为它取决于特定的机器，程序，时间，编译器和编程语言。 相反，我们希望有一个独立于所使用的程序或计算机的度量。这个度量将有助于独立地判断算法，并且可以用于比较不同实现方法的算法的效率。