iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
自我挑戰組

30天不怕演算法:白話文版系列 第 4

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.

上一篇
Day 03:如何分析演算法?
下一篇
Day 05:到底有多壞?演算法的最壞情況執行時間
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言