什么是大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表示法指出了最糟糕情况下的运行时间

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


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


说明

除最糟情况下的运行时间外,还应考虑平均情况的运行时间,这很重要。

一些常见的大O运行时间

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


O (log n ),也叫对数时间 ,这样的算法包括二分查找。

O (n ),也叫线性时间 ,这样的算法包括简单查找。

O (n * log n ),这样的算法包括快速排序——一种速度较快的排序算法。

O (n 2 ),这样的算法包括选择排序——一种速度较慢的排序算法。

O (n !),这样的算法包括旅行商问题的解决方案——一种非常慢的算法。


网友评论

0条评论

发表

网友评论

0条评论

发表

最新评论

推荐文章

彩龙

Copyright © 2008-2020 彩龙社区(https://www.clzg.cn) 版权所有 All Rights Reserved.

免责声明: 本网不承担任何由内容提供商提供的信息所引起的争议和法律责任。

经营许可证编号:滇B2-20090009-7

下载我家昆明APP 下载彩龙社区APP