引言
设计与开发程序时,我们需要考虑的最重要的一点就是,程序的结果必须正确。我们希望程序能正确计算银行余额,汽车喷油嘴能够喷出适量的燃料。不管是飞机还是操作系统,我们都不希望它们发生事故。
有时候,性能也是正确性的一个重要方面,特别是对于需要实时运行的程序,比如飞机上的障碍预警程序需要在遭遇障碍之前发出警告。性能也会影响很多非实时程序的使用效果。评价数据库系统的效用时,每分钟完成的事务数量是一个重要的指标。在智能手机上,用户会关系启动一个应用程序需要多长时间,而生物学家则关心系统进化推理计算会持续多久。
编写高效程序并不容易,最简单直接的方法一般都不是最有效率的。有效的算法一般都会使用一些巧妙的小技巧,这就使得它们非常难以理解。结果经常就是,程序员努力地减少了计算复杂度,但是却增加了概念复杂度。为了以合理的方式提高程序效率,我们应该知道如何估计一个程序的计算复杂度。
思考计算复杂度
首先,在我们考虑计算复杂度之间,我们先思考一个问题,运行下面这个函数需要多长时间。
我们可以使用一些输入来运行程序并计时,但结果并没有太大的意义,因为这样做的结果依赖于以下几个因素:
运行程序的计算机性能;
计算机上Python系统的效率;
输入值。
我们可以使用一种更加抽象的时间量度来解决前面两个问题。不再使用毫秒测量时间,而是以程序执行的基本步数为单位进行测量。
为了简单期间,我们使用随机存取机作为计算模型。在随机存取机中,步数是顺序执行的,每次执行一步,一步指的是一个需要固定时间量的操作,比如将变量绑定到对象、做一次比较、执行一次代数运算或访问内存中的对象。
既然我们已经使用了一种更抽象的方法来表示时间,下面就解决对输入值的依赖问题。不再用一个独立的数值表示时间复杂度,而是将时间复杂度与输入的规模联系起来。这样,比较两种算法的运行时间如何随着输入规模的增加而增加,即可比较两种算法的效率。
当然,算法的实际运行时间不仅依赖于输入规模,还依赖于具体的输入值。例如,考虑以下代码中实现的线性搜索算法:
假设L是一个包含100万一个元素的列表,我们看一个函数调用linearSearch(L, 3)。如果L中的一个元素是3,那么linearSearch几乎会立刻返回True。另一方面,如果3不在L中,那么linearSearch就必须在返回False之前,检查所有100万个元素。
一般而言,我们需要考虑三种常见的情形:
最佳情形运行时间是在输入最有利的情况下算法的运行时间。也就是说,在给定输入规模的情况下的最短的运行时间。对于linearSearch,最佳情形运行时间与L的大小无关。
最差情形运行时间是在给定输入规模的情况下最长的运行时间。对于linearSearch,最差情形运行时间与L的大小成正比。
平均情形(也被称为期望情形)运行时间是在给定输入规模的情况下的平均运行时间。此外,如果关于输入值的分布有一些先验信息(例如,在90%的情形下,x在L中),也应该将这些信息考虑在内。
领取专属 10元无门槛券
私享最新 技术干货