快快樂樂學 Big-O

對於資訊科系的人來說,也許會覺得 Big-O 到底有什麼好介紹的。不過隨著目前隨著寫程式的各種學習管道變多,非資訊科系背景的程式人越來越多,這篇文章的目標群眾就是這些人。
首先還是先來介紹一些基本的 Notation:
- O() -> 讀作 Order of
- N: Input 的資料量
另外講到 Big-O,有時候也會聽到有人說時間複雜度 (Time Complexity),或是複雜度 (Complexity) 等等。
什麼是 Big-O
用白話一點來說,到底什麼是 Big-O 呢?其實關於 Big-O,我們可以想成我們想要知道當程式資料量變多的時候,你的程式會變慢多少。Big-O 存在的目的是讓我們可以回答像是 「當我的資料量變成 100 倍的時候,我的程式執行時間會變幾倍?」這樣的問題。
真實世界的例子
關於 Big-O,我們可以舉兩個真實世界的例子讓大家更明白。
第一個例子是看書。看書的時候我們所需要的時間通常跟頁數成正比,假設我們看一頁的時間需要一分鐘,那麼兩百頁的書需要兩百分鐘,一千頁的書需要一千分鐘。因此,看書的例子我們會說是 O(N),在這邊,N 是頁數。
第二個例子是在通訊錄當中尋找某個聯絡人。通常我們的通訊錄會照著字母排序,在尋找聯絡人的時候,每次可以捨棄一半的資料。這個例子中我們會說這個動作是 O(log N)。在這,N 是通訊錄中聯絡人的人數。
常看到的幾種 Big-O
下圖可以看到幾個常見的 Big-O,我們可以看到 O(N^2), O(N log N), O(n), O(log N) 這幾個不同 Big-O 隨著 N 變大,成長速度也會差很多的現象

怎麼計算 Big-O
前面我們大概介紹了基本的 Big-O 概念,那麼如果套用到我們寫的程式上面,要如何得知我們程式的 Big-O?基本上可以分成簡單的四個步驟:
- 選定一段程式碼
- 決定你的 Input 大小 N
- 計算你的程式要跑幾個步驟
- 只留下影響最大的部分,當作這段程式的 Big-O
下面舉兩個簡單的例子。
def big_o_n(items):
for item in items:
print(item)
上面這個例子是個最簡單的 iteration,我們的 Input Size N 是 items 的個數,總共會跑 N 次,所以這段程式碼的 Big-O 是 O(N)
def big_o_n_square(items):
for item in items:
for item2 in items:
print(item)
for item in items:
print(item)
print(items[0])
print(items[1])
上面這個例子則是稍微複雜一些些。2-4 行會跑 N^2 次,6-7 行會跑 N 次,9, 10 行則分別會跑 1 次。因此總共會跑 N^2+N+2 次,這邊影響最大的部分是 N^2,因此這段程式碼是 O(N^2)
Python 與 Big-O
在實務上,我們的程式不會都是這麼單純的例子,常常我們會使用到 Python 當中的許多內建 library。要如何得知這些 library 的時間複雜度呢?好在 Python 官方有列出一份 wiki 讓大家可以參考。在選擇 Python 內建 library 的時候,就可以依照自己的需求來使用適當的 Data Structure 以及 operation。
結論
這篇文章簡單的介紹了 Big-O 是什麼,也知道了要怎麼計算 Big-O。雖然時間複雜度對於寫程式來說是個重要的觀念,但是實務上還是要配合各種 profiling tool 來使用。
記住 80/20 法則,你的程式大多數的時間都會耗在某一小段程式上面,所以不用斤斤計較每一段程式的 Big-O,只要專注在會影響效能的那段就好。