二分查找

一般而言，对于包含n个元素的列表，
用二分查找最多需要步，简单查找最多需要n步。

对数

相当于问将多少个10相乘的结果为100?

答案：,因此，。

对数运算是幂运算的逆运算：

运行时间

大O表示法是一种特殊的表示法，指出了算法的速度有多快，
大O表示法指出了最糟情况下的运行时间

5种大O运行时间。

• ，也叫对数时间（或log时间），包括二分查找。
• ，线性时间（linear time），包括简单查找。
• ，快速排序一种速度较快的排序算法。
• ，选择排序一种速度较慢的排序算法。
• ，旅行商问题一种非常慢的算法。

小结

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大O表示法表示。

脚注

1. 使用大O表示法，指的都是
2. ：n的阶乘，亦即n!=1×2×3×…×n