Day 04：大O符号的含意

上一回提到大O符号表达执行时间，但对於大O符号我们可能有些疑问。

既是叫时间，那它的单位是什麽？

我们可以在演算法的例子中加入时间来比较一下。

如果今天有一个有100个数字的阵列，我们要在当中找到一个数字。用线性搜寻的话，最多100次操作找到；用二分搜寻则最多7次找到。假设每个步骤要花一毫秒，两种搜寻分别要用100毫秒和7毫秒，基本上都是一瞬间就完成了，感觉不太出差别。

可是现实案例的输入会大上很多。

假设输入的阵列变成有一亿个元素，线性搜寻变成要花一亿毫秒，相当於要不眠不休持续运算超过24小时，而二分搜寻需要只要大约26毫秒，也是一瞬间就完成。

如果输入再大一点，变成十亿呢？线性搜寻需要超过11天，而二分搜寻却只要约30毫秒，依然还是一瞬间就完成了。

这样的比较告诉我们一件重要的事情：

大O符号表达的执行时间没有秒或毫秒这些单位，因为它的重点并不是在於特定输入时的执行时间。它的重点在於随着输入变大，执行时间会增加多快。

当输入从100个元素，变成一亿个，再变成十亿个，O(n)增加很多，O(logn)却只增加一点点点点，这个差距并不是操作秒数多寡可以影响的。事实上，就算二分搜寻的每个步骤要花到一秒好了，操作十亿个元素也只是从30毫秒变成30秒，还是远远快於O(n)的11天，说明了两种执行时间因为增加速度的不同而有根本上的差距。

Algorithms Illuminated 这本书[注1]有很精简的总结：如果一个演算法的最坏情况执行时间随着输入成长得很缓慢，它就算是一个「快的演算法」。

A “fast algorithm” is an algorithm whose worst-case
running time grows slowly with the input size.

为什麽log2 n个步骤写成执行时间变成O(log n)？

其实这题有点像上一题的延续。上一题提到，不同的执行时间之间有极大差异，而且这个差异会随着输入变大而更显着，所以讨论执行时间时，通常只会关注会随输入变大会明显变大的数字，并且忽略其中的常数，也就是那些不会因为输入变大而改变的数字。

举例来说，假设玩定时炸弹时，我们用奇数(1, 3, 5, 7...)来猜，因为一次跳两个数字，应该最多猜50次就会猜到，所以执行时间应该是原本的一半O(n/2)，感觉变快很多。

可是当输入变成十亿，O(n/2)最多仍然要五亿次操作，跟O(log n)的30次还是完全不能比，所以在输入非常大时，可以当作常数(1/2)不会有什麽影响。

因此当用大O符号讨论执行时间时，只会留下有决定性影响的部分，去掉常数以及影响较小的n项。例如不管操作次数是n/2或5n+3，仍会说它的执行时间是O(n)；如果是 3n³+n+1，则会说它的执行时间是O(n³)(只留下最高次方的n项)。当然log的底数也是因为同样原因被去掉，只留下O(log n)。

另外，在执行时间中我们也会看到比较特别的O(1)，代表一个演算法具有常数时间(constant time)。它的意思并不是绝对只要一次操作就可以完成，实际上也有可能是五次或十次，但常数时间的重点在於执行时间不会随着输入变大而增加。例如说当我搜寻通讯录，如果只要输入朋友的名字「王小新」就可以找到他的电话，那麽无论通讯录多长，操作时间都不会变，就可以说这个搜寻是O(1)。

• [注1]Tim Roughgarden, Algorithms Illuminated Part 1: The Basics, Soundlikeyourself Publishing, 2017, page 30.