2.1.⽬标·了解为何算法分析的重要性·能够⽤⼤“O ”表⽰法来描述算法执⾏时间·了解在Python 列表和字典类型中通⽤操作⽤⼤“O ”表⽰法表⽰的执⾏时间·了解Python 数据类型的具体实现对算法分析的影响·了解如何对简单的Python 程序进⾏执⾏时间检测2.2.什么是算法分析计算机初学者经常将⾃⼰的程序与他⼈的⽐较。

你也可能注意到了电脑程序常常看起来很相似，尤其是那些简单的程序。

⼀个有趣的问题出现了，当两个看起来不同的程序解决相同的问题时，⼀个程序会优于另⼀个吗？为了回答这个问题，我们需要记住的是，程序和它所代表的基本算法有着重要差别。

在第⼀章中我们说到，算法是问题解决的通⽤的分步的指令的聚合。

这是⼀种能解决任何问题实例的⽅法，⽐如给定⼀个特定的输⼊，算法能产⽣期望的结果。

从另⼀⽅⾯看，⼀个程序是⽤某种编程语⾔编码后的算法。

同⼀算法通过不同的程序员采⽤不同的编程语⾔能产⽣很多程序。

为进⼀步探究这种差异，请阅读接下来展⽰的函数。

这个函数解决了⼀个我们熟知的问题，计算前n 个整数的和。

其中的算法使⽤了⼀个初始值为0的累加变量的概念。

解决⽅案是遍历这n 个整数，逐个累加到累加变量。

代码2.1前n 个正整数求和（active1）现在看下⾯的foo函数。

可能第⼀眼看上去⽐较奇怪，但是进⼀步观察你会发现，这个函数所实现的功能与之前代码2.1中的函数基本相同。

看不太懂的原因是糟糕的编码。

我们没有使⽤好的变量命名来增加可读性，并且在累加过程中使⽤了多余的赋值语句。

回到前⾯我们提出的问题：是否⼀个程序会优于另⼀个？答案取决于你⾃⼰的标准。

如果你关⼼可读性，那么sum_of_n函数肯定⽐foo函数更好。

实际上，在你的编程⼊门课程上你可能见过很多这样的例⼦，因为这些课程的⽬标之⼀就是帮助你编写更具可读性的程代码2.2 另⼀种前n个正整数求和（ac ve2）def foo(tom):fred=0for bill in range(1,tom+1):barney = billfred = fred + barneyreturn fredprint (foo(10))序。

然⽽，在这门课程中，我们主要感兴趣的是算法本⾝的特性。

（我们当然希望你可以继续努⼒写出更具可读性的代码。

）算法分析主要就是从计算资源的消耗的⾓度来评判和⽐较算法。

我们想要分析两种算法并且指出哪种更好，主要考虑的是哪⼀种可以更⾼效地利⽤计算资源。

或者占⽤更少的资源。

从这个⾓度，上述两个函数实际上是基本相同的，它们都采⽤了⼀样的算法来解决累加求和问题。

从这点上看，思考我们通过计算资源这个概念真正想表达的是什么是⾮常重要的。

有两种⽅法来看待它。

⼀种是考虑算法解决问题过程中需要的存储空间或内存。

问题解决⽅案所需的存储空间通常是由问题本⾝情况影响的，然⽽，算法常常有本⾝特定的空间需求，在这种情况下，我们需要很⼩⼼地解释这种变化。

作为空间需求的⼀个可替代物，我们可以⽤算法执⾏所需时间来分析和⽐较算法。

这种⽅法有时被称为算法的“执⾏时间”或“运⾏时间”。

我们可以检测sum_of_n函数的运⾏时间的⼀种⽅法是做基准分析。

这意味着我们将监测程序运⾏出结果所需要的时间。

在Python中，我们可以考虑我们使⽤的系统通过标定开始时间和结束时间来作为标准衡量⼀个函数。

在 me模块有⼀个叫 me的函数，它能返回在某些任意起点以秒为单位的系统当前时间。

通过在开始和结束时两次调⽤这个函数，然后计算两次时间之差，我们就可以得到精确到秒（⼤多数情况为分数）的运⾏时间。

这个编码展⽰了在原始sum_of_n函数的求和前后插⼊时间调⽤的情况。

这个函数返回⼀个元组，包括累加和及计算所需时间（以秒为单位）。

如果我们连续运⾏这个函数5次，每次都完成1到10,000的累加，我们得到的结果如下：>>>for i in range(5):Print(“Sum is %d required %10.7f seconds”% sum_of_n_2(10000))Sum is 50005000 required 0.0018950 secondsSum is 50005000 required 0.0018620 secondsSum is 50005000 required 0.0019171 secondsSum is 50005000 required 0.0019162 secondsSum is 50005000 required 0.0019360 seconds>>>我们发现这个时间是相当⼀致的，执⾏这段代码平均需要0.0019秒。

那么如果我们累加到100,000会怎么样呢？⼜是这样，每次运⾏所需时间虽然更长，但⾮常⼀致，平均约为之前的10倍，进⼀步累加到1,000,000我们得到：在这种情况下，平均时间再次约为之前的10倍。

现在考虑接下来的编码，它展⽰了⼀种解决求和问题的不同的⽅法。

这个函数，sum_of_n_3,利⽤⼀个封闭⽅程去完成⽆迭代的累加到n 的计算。

代码2.3 ⽆迭代求和 >>>for i in range(5):Print(“Sum is %d required %10.7f seconds”% sum_of_n_2(100000))Sum is 5000050000 required 0.0199420 secondsSum is 5000050000 required 0.0180972 secondsSum is 5000050000 required 0.0194821 secondsSum is 5000050000 required 0.0178988 secondsSum is 5000050000 required 0.0188949 seconds>>> >>>for i in range(5):Print(“Sum is %d required %10.7f seconds”% sum_of_n_2(1000000)) Sum is 500000500000 required 0.1948988 secondsSum is 500000500000 required 0.1850290 secondsSum is 500000500000 required 0.1809771 secondsSum is 500000500000 required 0.1729250 seconds Sum is 500000500000 required 0.1646299 seconds>>>def sum_of_n_3(n):return (n * (n +1)) / 2print (sum_of_n_3(10))如果我们对sum_of_n_3做同样的基准检测，n赋5个不同的值（10000,100000,1000000,10000，000和100000000），我们得到的结果如下:Sum is 50005000 required 0.00000095 secondsSum is 5000050000 required 0.00000191 secondsSum is 500000500000 required 0.00000095 secondsSum is 50000005000000 required 0.00000095 secondsSum is 5000000050000000 required 0.00000119 seconds对于输出我们需要关注两个关键点。

第⼀，这种算法的运⾏时间⽐之前任何例⼦都短很多。

第⼆，不管n取值多少运⾏时间都⾮常⼀致。

看上去sum_of_n_3的运⾏时间⼏乎不受需要累计的数⽬的影响。

但是这个基准测试真正告诉了我们什么？直观上，我们可以看到迭代算法似乎做了更多的⼯作，因为⼀些程序步骤被重复执⾏，这可能就是它需要更长时间的原因。

此外，迭代算法所需要的运⾏时间似乎会随着n值的增⼤⽽增⼤。

然⽽，还有⼀个问题。

如果我们在不同的计算机上运⾏相同的函数，或者使⽤不同的编程语⾔，我们可能会得到不同的结果。

如果计算机⽐较⽼旧，运⾏sum_of_n_3可能还需要更长的时间。

我们需要更好的⽅法来衡量算法运⾏的时间。

基准测试技术可以计算世界运⾏时间，然⽽它并没有真的为我们提供⼀个有⽤的度量指标。

因为这个指标依赖于特定的机器、程序、运⾏时段、编译器和编程语⾔。

相反，我们需要⼀个不依赖程序或者使⽤的机器的指标。

这种度量指标将有助于判断算法优劣，并且可以⽤来⽐较算法的具体实现。

2.2.1. ⼤“O”表⽰法当我们试图⽤执⾏时间作为独⽴于具体程序或计算机的度量指标去描述⼀个算法的效率时，确定这个算法所需要的操作数或步骤数显得尤为重要。

如果把每⼀⼩步看作⼀个基本计量单位，那么⼀个算法的执⾏时间就可以表达为它解决⼀个问题所需的步骤数。

制定⼀个合适的基本计量单位是⼀个很复杂的问题，并且还要依赖于算法具体是怎样执⾏的。

当我们⽐较上述⼏个求和算法时，统计执⾏求和的赋值语句的次数可能是⼀个好的基本计量单位。

在sum_of_n函数中，赋值语句的数量是1（the_sum=0）加上n（我们执⾏the_sum=the_sum+i 的次数）。

我们可以⽤⼀个叫T的函数来表⽰赋值语句数量，如上例中T(n) = 1 + n。

变量n⼀般指“问题的规模”，可以理解为当要解决⼀个规模为n，对应n+1步操作步数的问题，所需要的时间为T(n)。

在前⼀节给出的求和函数中，⽤求和的项数来代表问题的规模是合理的。

可以认为求前100000项整数的问题规模⼤于求前1000项整数。

因此，求解⼤规模问题所需时间显然⽐求解⼩规模要多⼀些。

那么我们的⽬标就是寻找程序的运⾏时间如何随着问题规模变化。

计算机科学家对这种算法分析技术进⾏了更为深远的思考。

有限的操作次数对于T(n)函数的影响，并不如某些占据主要地位的操作部分重要。

换⾔之，当问题规模越来越⼤时，T(n)函数中的⼀部分⼏乎掩盖了其他部分对于函数的影响。

最终，这种起主导作⽤的部分⽤来对函数进⾏⽐较。

数量级函数⽤来描述当规模n增加时，T(n)函数中增长最快的部分。

这种数量级函数⼀般被称为⼤“O”表⽰法，记作O(f(n))。

它提供了计算过程中实际步数的近似值。

函数f(n)是原始函数T(n)中主导部分的简化表⽰。

在上⾯的例⼦中，T(n) = 1 + n。

当n增⼤时，常数1对于最后的结果来说越来越不重要。

如果我们需要T(n)的近似值，我们可以忽略常数1，直接认为T(n)的运⾏时间就是O(n)。