时间复杂度 O(log n) 意味着什么？

原文地址：What does the time complexity O(log n) actually mean?open in new window

事先了解算法的复杂性是一回事，了解其背后的原因是另一回事。

无论你是计算机科学专业的毕业生，还是想要有效处理优化问题的人，如果你想利用你的知识解决实际问题，这是你必须理解的东西。

先从简单直观的 $O(1)$ 和 $O(n)$ 复杂度说起。 $O(1)$ 表示一次操作即可直接取得目标元素（比如字典或哈希表）， $O(n)$ 意味着先要检查 $n$ 个元素来搜索目标，但是 $O(logn)$ 是什么意思呢？

你第一次听说 $O(log n)$ 时间复杂度可能是在学二分搜索算法的时候。二分搜索一定有某种行为使其时间复杂度为 $log n$ 。我们来看看是二分搜索是如何实现的。

因为在最好情况下二分搜索的时间复杂度是 $O(1)$ ，最坏情况（平均情况）下 $O(logn)$ ，我们直接来看最坏情况下的例子。已知有 16 个元素的有序数组。

举个最坏情况的例子，比如我们要找的是数字 13。

1	3	5	8	12	13	15	16	18	20	22	30	40	50	55	67
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

十六个元素的有序数组

1	3	5	8	12	13	15	16	18	20	22	30	40	50	55	67
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
							$\uparrow$

选中间的元素作为中心点（长度的一半）: $16 \times \frac{1}{2} = 8$

1	3	5	8	12	13	15	16
0	1	2	3	4	5	6	7

13 小于中心点，所以不用考虑数组的后一半: $8 \times \frac{1}{2} = 4$

12	13	15	16

重复这个过程，每次都寻找子数组的中间元素

$4 \times \frac{1}{2} = 2$

12	13

$2 \times \frac{1}{2} = 1$

13

每次和中间元素比较都会使搜索范围减半。

所以为了从 16 个元素中找到目标元素，我们需要把数组平均分割 4 次，也就是说，

$16 \times (\frac{1}{2})^4 = 1$

简化后的公式

类似的，如果有 n 个元素，

$n \times (\frac{1}{2})^k = 1$

归纳一下

$n \times \frac{1}{2^k} = 1$

分子和分母代入指数

$2^k \times \frac{n}{2^k} = 2^k$

等式两边同时乘以 $2^k$

$n =2^k$

最终结果

现在来看看「对数」的定义：

为使某数（底数）等于一给定数而必须取的乘幂的幂指数。

也就是说可以写成这种形式

$log_2\,n = k$

对数形式

所以 $log n$ 的确是有意义的，不是吗？没有其他什么可以表示这种行为。

就这样吧，我希望我讲得这些你都搞懂了。在从事计算机科学相关的工作时，了解这类知识总是有用的（而且很有趣）。说不定就因为你知道算法的原理，你成了小组里能找出问题的最优解的人呢，谁知道呢。祝好运！

# 时间复杂度 O(log n) 意味着什么？