2.2.什么是算法分析

一些普遍的现象是，刚接触计算机科学的同学会将自己的程序和其他的相比较。你可能还注意到，计算机程序看起来很相似，尤其是简单的程序。经常出现一个有趣的问题。当两个程序解决同样的问题，但看起来不同，哪一个更好呢？为了回答这个问题，我们需要记住，程序和程序代表的底层算法之间有一个重要的区别。正如我们在第 1 章中所说，一个算法是一个通用的，解决问题的指令列表。它是用于解决问题的任何实例的方法，给定特定输入，产生期望的结果。另一方面，程序是已经被编码成某种编程语言的算法。根据所使用的编程器和编程语言，可能存在用于相同算法的许多程序。要进一步探讨这种差异，请参考 ActiveCode 1 中显示的函数。这个函数解决了一个熟悉的问题，计算前 n 个整数的和。该算法使用初始化为 0 的累加器变量。然后迭代 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 中的函数。乍一看，它可能很奇怪，但进一步的观察，你可以看到，这个功能本质上和前面的程序做同样的事情。不直观的原因在于编码习惯不好。我们没有使用良好的标识符名称来提升可读性，我们在迭代步骤中使用了一个额外的赋值语句，这并不是真正必要的。

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 好。事实上，你可能已经在介绍编程的课程中看到过很多例子，他们的目标之一就是帮助你编写易于阅读和理解的程序。在本课程中，我们对如何表示算法感兴趣（当然我们希望你继续努力编写可读的，易于理解的代码）。

算法分析涉及基于每个算法使用的计算资源量来比较算法。我们比较两个算法，说一个比另一个算法好的原因在于它在使用资源方面更有效率，或者仅仅使用的资源更少。从这个角度来看，上面两个函数看起来很相似。它们都使用基本相同的算法来求解问题。在这点上，更重要的是我们如何考虑真正意义上的计算资源。有两种方法，一种是考虑算法所需的空间或者内存。所需的空间通常由问题本身决定。但是，算法会有一些特殊的空间需求，我们可以细细观察解释这些变动。

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

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

Listing 1 嵌入了时间函数，函数返回一个包含结果和消耗时间的数组。如果我们执行这个函数 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，它显示了求解求和问题的不同方法

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

print(sumOfN3(10))

ActiveCode 3

如果我们对 sumOfN3 做同样的基准测试，使用 5 个不同的 n (10,000, 100,000, 1,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。

我们需要一个更好的方法来表征这些算法的执行时间。基准测试计算的是执行的实际时间。它并不真正提供给我们一个有用的测量，因为它取决于特定的机器，程序，时间，编译器和编程语言。 相反，我们希望具有独立于所使用的程序或计算机的特性。不过基准度量将有助于单独判断算法，并且可以用于在方案之间比较算法。