什么是大 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群号:855454453

Q855454453