算法的时间复杂度(大O表示法)
首先我们先来看个例子, 我想找个1~100的数字`,你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。下面我们来看下两种简单的方法(方法有很多种),再来引入算法的运行时间!``
方法一(循环遍历):
假设你从1开始依次往上猜,猜测过程会是这样!
这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99,
你得猜99次才能猜到!
方法二(二分查找):
(如果我想的数字是99)首先从100中 找到中间的值50,然后和50比较,小了?继续找中间值75,和75比较,小了?,继续找中间值88,和88比较,小了?继续找中间值94,和94比较,小了?继续找中间值97,和97比较,小了?继续找中间值99,和99比较,相等!最终找到了99这个数字!
使用二分查找时,每次都排除一半的数字!不管是哪个数字,你在7次之内都能猜到,因为每次猜测都将排除很多数字!对于包含n个元素的列表,用二分查找最多需要
log
2
n
\log_2 n
log2n步,而简单查找最多需要n步。
你可能不记得什么是对数了,但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此,log10100 = 2。对数运算是幂运算的逆运算。
2 2 ↔ \leftrightarrow ↔ l o g 2 4 {log_2{4}} log24 = 2 2 3 ↔ \leftrightarrow ↔ l o g 2 8 {log_2{8}} log28 = 3 2 4 ↔ \leftrightarrow ↔ l o g 2 16 {log_2{16}} log216 = 4 对数是幂运算的逆运算 讨论运行时间时,log指的都是log2。使用简单查找法查找元素时,在最糟情况下需要查看每个元素。因此,如果列表包含8个数字,你最多需要检查8个数字。而使用二分查找时,最多需要检查log n个元素。如果列表包含8个元素,你最多需要检查3个元素,因为log 8 = 3(2 3 = 8)。如果列表包含1024个元素,你最多需要检查10个元素,因为log 1024 = 10(2 10 =1024)。`
大O 表示法
大O表示法是一种特殊的表示法,指出了算法的速度有多快。实际上,你经常要使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。下面将介绍大O表示法是什么,并使用它列出一些最常见的算法运行时间。还是先来看个小例子!需要编写一个查找算法, 这个算法在火箭即将登陆月球前开始执行,帮助计算着陆地点,必须在10秒钟内找出着陆地点,否则火箭将偏离方向!为确保万无一失,Bob需要计算列表包含100个元素的情况下需要的时间!
例子分析:
假设检查一个元素需要1毫秒。使用简单查找时,必须检查100个元素,因此需要100毫秒才能查找完毕。而使用二分查找时,只需检查7个元素(
l
o
g
2
100
log_2100
log2100大约为7),因此需要7毫秒就能查找完毕。然而,实际要查找的列表可能包含10亿个元素,在这种情况下,简单查找需要多长时间呢?二分查找又需要多长时间呢?Bob使用包含10亿个元素的列表运行二分查找,运行时间为30毫秒(log21 000 000 000大约为30)。他心里想,二分查找的速度大约为简单查找的15倍,因为列表包含100个元素时,简单查找需要100毫秒,而二分查找需要7毫秒。因此,列表包含10亿个元素时,简单查找需要30 × 15 = 450毫秒,完全符合在10秒内查找完毕的要求。Bob决定使用简单查找。这是正确的选择吗?不是。实际上,Bob错了,而且错得离谱。列表包含10亿个元素时,简单查找需要10亿毫秒,相当于11天!为什么会这样呢?因为二分查找和简单查找的运行时间的增速不同。
也就是说,随着元素数量的增加,二分查找需要的额外时间并不多,而简单查找需要的额外时间却很多。因此,随着列表的增长,二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍,这不对:列表包含10亿个元素时,为3300万倍!有鉴于此,仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。
大O表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n),二分查找需要执行
l
o
g
2
n
log_2 n
log2n次操作。使用大O表示法,这个运行时间怎么表示呢?O(
l
o
g
2
n
log_2 n
log2n),单位秒呢?大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数,它指出了算法运行时间的增速。一般而言,大O表示法像下面这样:
这指出了算法需要执行的操作数。之所以称为大O表示法,是因为操作数前有个大O!
一些常见的大O 运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
- O(log n),也叫对数时间,这样的算法包括二分查找。
- O(n),也叫线性时间,这样的算法包括简单查找。
- O(n * log n),快速排序——一种速度较快的排序算法。
- O(n2),选择排序——一种速度较慢的排序算法。
- O(n!),一种非常慢的算法。
这些算法不懂可以点击这里,再看下例子,假设你要绘制一个包含16格的网格,且有5种不同的算法可供选择,这些算法的运行时间如上所示。如果你选择第一种算法,绘制该网格所需的操作数将为4(log 16 = 4)。假设你每秒可执行10次操作,那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢?这需要执行10(log 1024 = 10)次操作,换言之,绘制这样的网格需要1秒。这是使用第一种算法的情况。第二种算法更慢,其运行时间为O(n)。即要绘制16个格子,需要执行16次操作;要绘制1024个格子,需要执行1024次操作。执行这些操作需要多少秒呢?下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:
还有其他的运行时间,但这5种是最常见的。这里做了简化,实际上,并不能如此干净利索地将大O运行时间转换为操作数,但就目前而言,这种准确度足够了。等学习其他一些算法后,回过头来再次讨论大O表示法。
大O 运行时间平均情况,最佳情况和最糟情况
就拿快速排序来说吧!假设你总是将第一个元素用作基准值,且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序,因此它依然尝试对其进行排序。
注意,数组并没有被分成两半,相反,其中一个子数组始终为空,这导致调用栈非常长。现在假设你总是将中间的元素用作基准值,在这种情况下,调用栈如下。
调用栈短得多!因为你每次都将数组分成两半,所以不需要那么多递归调用。你很快就到达
了基线条件,因此调用栈短得多。第一个示例展示的是最糟情况,而第二个示例展示的是最佳情况。在最糟情况下,栈长为O(n),而在最佳情况下,栈长为O(log n)。现在来看看栈的第一层。你将一个元素用作基准值,并将其他的元素划分到两个子数组中。这涉及数组中的全部8个元素,因此该操作的时间为O(n)。在调用栈的第一层,涉及全部8个元素,但实际上,在调用栈的每层都涉及O(n)个元素。
即便以不同的方式划分数组,每次也将涉及O(n)个元素。
因此,完成每层所需的时间都为O(n)。
在这个示例中,层数为O(log n)(用技术术语说,调用栈的高度为O(log n)),而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。在最糟情况下,有O(n)层,因此该算法的运行时间为O(n) * O(n) = O(n2)。这里要告诉你的是,最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值,快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一,也是D&C典范(divide and conquer 分而治之)
总结:
- 算法的速度指的并非时间,而是操作数的增速。
- 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- 例子中O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。