什么是大 O 表示法

“大O表示法”是一种特殊的表示法，指出了算法的速度有多快。但是它却不是指具体的时间，那么该如何正确理解它呢？

算法的运行时间以不同的速度增加

“算法的运行时间以不同的速度增加”这句话应该如何理解呢？下面我们通过🌰来看看这句话到底想表达什么。

小明现在需要编写一个查找算法，这个算法服务于学校图书馆，目的是帮助童鞋们能够快速的找到自己需要的书籍所在位置。

假设小明现在只会“二分查找”和“简单查找”。一方面，二分查找的速度很快，小明必须在 10 秒钟内找到书籍所在位置，否则童鞋们没有更多耐心等待。另一方面，简单查找算法编写起来更容易，因此出现 bug 的可能性更小。

为了检验这两种算法的耗时，小明决定计算两种算法在列表包含 100 个元素的情况下需要的时间。

假设检查一个元素需要 1 毫秒。使用简单查找时，小明必须检查 100 个元素，因此需要 100 毫秒才能查找完毕。而使用二分查找时，只需检查 7 个元素（log2 100大约为7），因此需要 7 毫秒就能查找完毕。然而，实际要查找的列表可能包含 10 亿个元素，在这种情况下，简单查找需要多长时间呢？二分查找又需要多长时间呢？

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

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

简单查找	二分查找	元素个数
100 毫秒	7 毫秒	100
10 秒	14 毫秒	10 000
11 天	30 毫秒	1 000 000 000

随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。小明以为二分查找速度为简单查找的 15 倍，这不对：列表包含 10 亿个元素时，为 3300 万倍。有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。

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

最糟糕情况下的运行时间

假设你使用简单查找在电话簿中找人。你知道，简单查找的运行时间为 O(n)，这意味着在最糟情况下，必须查看电话簿中的每个条目。如果要查找的是 Chars ——电话簿中的第一个人，一次就能找到，无需查看每个条目。考虑到一次就找到了 Chars，请问这种算法的运行时间是 O(n)还是 O(1) 呢？

简单查找的运行时间总是为 O(n)。查找 Chars 时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为 O(n)。这是一个保证——你知道简单查找的运行时间不可能超过 O(n)。

说明

除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在第4章讨论。

一些常见的大O运行时间

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

• O (log n )，也叫对数时间 ，这样的算法包括二分查找。
• O (n )，也叫线性时间 ，这样的算法包括简单查找。
• O (n * log n )，这样的算法包括快速排序——一种速度较快的排序算法。
• O (n 2 )，这样的算法包括选择排序——一种速度较慢的排序算法。
• O (n !)，这样的算法包括旅行商问题的解决方案——一种非常慢的算法。

总结

1、算法的速度指的并非时间，而是操作数的增速。

2、谈论算法的速度时，说的是随着输入的增加，其运行时间将以什么样的速度增加。

3、算法的运行时间用大O表示法表示。

4、O(log n) 比 O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

写在最后

对算法有兴趣的童鞋可以关注专栏《通俗易懂的算法》，也欢迎大家多多投稿分享。

同时欢迎大家加入移动开发交流Q群交流讨论，Q群号：811237468