一. 运行时间

        每次介绍算法时，我们都将讨论其运行时间。一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。

        可是，如果代码都还没有运行，我怎么能预知代码运行所花的时间呢？

        由于受运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。

诸如二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。

二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。下表总结了我们发现的情况。

二. 大O 表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。谁会在乎运算速度呢？实际上，你经常要使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益。本节将介绍大O表示法是什么，并使用它列出一些最常见的算法运行时间

为了解决时间分析的难题，有了渐进时间复杂度（asymptotic time complexity）的概念，其官方定义如下：

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示；若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。

因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

概念有点晦涩，我们使用下面的这个示例来理解一下

2.1 示例

通过以下示例，来理解算法的运行时间以不同的速度增加：

        小明要为“嫦娥5号”编写一个查找算法，这个算法在火箭即将登陆月球前开始执行，帮助计算着陆地点。

        前面示例表明，简单查找和二分查找这两种算法的运行时间呈现不同的增速。小明需要做出决定，是使用简单查找还是二分查找。使用的算法必须快速而准确。

        一方面，二分查找的速度更快。小明必须在10秒钟内找出着陆地点，否则火箭将偏离方向。另一方面，简单查找算法编写起来更容易，因此出现bug的可能性更小。小明可不希望引导火箭着陆的代码中有bug！为确保万无一失，小明决定计算两种算法在列表包含100个元素的情况下需要的时间。

        假设检查一个元素需要1毫秒。使用简单查找时，小明必须检查100个元素，因此需要100毫秒才能查找完毕。而使用二分查找时，只需检查7个元素（log2100 大约为7），因此需要7毫秒就能查找完毕。

然而，实际要查找的列表可能包含10亿个元素，在这种情况下，简单查找需要多长时间呢？二分查找又需要多长时间呢？请务必找出这两个问题的答案，再继续。

使用包含10亿个元素的列表运行二分查找，运行时间为30毫秒（log21 000 000 000大约为30）。小明心里想，二分查找的速度大约为简单查找的15倍，因为列表包含100个元素时，简单查找需要100毫秒，而二分查找需要7毫秒。因此，列表包含10亿个元素时，简单查找需要30 × 15 = 450毫秒，完全符合在10秒内查找完毕的要求。小明决定使用简单查找。这是正确的选择吗？

不是。实际上，小明错了，而且错得离谱。列表包含10亿个元素时，简单查找需要10亿毫秒，相当于11天！为什么会这样呢？因为二分查找和简单查找的运行时间的增速不同。

也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍，这不对：列表包含10亿个元素时，为3300万倍。

有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

再来看一个例子。为检查长度为n的列表，二分查找需要执行log2n 次操作。使用大O表示法，这个运行时间怎么表示呢？O(log2n)。一般而言，大O表示法像下面这样。

这指出了算法需要执行的操作数。之所以称为大O表示法，是因为操作数前有个大O。这听起来像笑话，但事实如此！

三. 总结

        有了基本操作执行次数的函数T(n)，无法直接分析和比较代码的运行时间。

        例如算法A的执行次数是T(n)= 100n，算法B的执行次数是T(n)= 5n2，这两个函数到底谁的运行时间更长一些，需要看n的取值。

        因此，大O表示法就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n2、n3等。