Python编程之算法复杂度

引言

设计与开发程序时，我们需要考虑的最重要的一点就是，程序的结果必须正确。我们希望程序能正确计算银行余额，汽车喷油嘴能够喷出适量的燃料。不管是飞机还是操作系统，我们都不希望它们发生事故。

有时候，性能也是正确性的一个重要方面，特别是对于需要实时运行的程序，比如飞机上的障碍预警程序需要在遭遇障碍之前发出警告。性能也会影响很多非实时程序的使用效果。评价数据库系统的效用时，每分钟完成的事务数量是一个重要的指标。在智能手机上，用户会关系启动一个应用程序需要多长时间，而生物学家则关心系统进化推理计算会持续多久。

编写高效程序并不容易，最简单直接的方法一般都不是最有效率的。有效的算法一般都会使用一些巧妙的小技巧，这就使得它们非常难以理解。结果经常就是，程序员努力地减少了计算复杂度，但是却增加了概念复杂度。为了以合理的方式提高程序效率，我们应该知道如何估计一个程序的计算复杂度。

思考计算复杂度

首先，在我们考虑计算复杂度之间，我们先思考一个问题，运行下面这个函数需要多长时间。

我们可以使用一些输入来运行程序并计时，但结果并没有太大的意义，因为这样做的结果依赖于以下几个因素：

运行程序的计算机性能；

计算机上Python系统的效率；

输入值。

我们可以使用一种更加抽象的时间量度来解决前面两个问题。不再使用毫秒测量时间，而是以程序执行的基本步数为单位进行测量。

为了简单期间，我们使用随机存取机作为计算模型。在随机存取机中，步数是顺序执行的，每次执行一步，一步指的是一个需要固定时间量的操作，比如将变量绑定到对象、做一次比较、执行一次代数运算或访问内存中的对象。

既然我们已经使用了一种更抽象的方法来表示时间，下面就解决对输入值的依赖问题。不再用一个独立的数值表示时间复杂度，而是将时间复杂度与输入的规模联系起来。这样，比较两种算法的运行时间如何随着输入规模的增加而增加，即可比较两种算法的效率。

当然，算法的实际运行时间不仅依赖于输入规模，还依赖于具体的输入值。例如，考虑以下代码中实现的线性搜索算法：

假设L是一个包含100万一个元素的列表，我们看一个函数调用linearSearch(L, 3)。如果L中的一个元素是3，那么linearSearch几乎会立刻返回True。另一方面，如果3不在L中，那么linearSearch就必须在返回False之前，检查所有100万个元素。

一般而言，我们需要考虑三种常见的情形：

最佳情形运行时间是在输入最有利的情况下算法的运行时间。也就是说，在给定输入规模的情况下的最短的运行时间。对于linearSearch，最佳情形运行时间与L的大小无关。

最差情形运行时间是在给定输入规模的情况下最长的运行时间。对于linearSearch，最差情形运行时间与L的大小成正比。

平均情形（也被称为期望情形）运行时间是在给定输入规模的情况下的平均运行时间。此外，如果关于输入值的分布有一些先验信息（例如，在90%的情形下，x在L中），也应该将这些信息考虑在内。