快快樂樂學 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？基本上可以分成簡單的四個步驟：

1. 選定一段程式碼
2. 決定你的 Input 大小 N
3. 計算你的程式要跑幾個步驟
4. 只留下影響最大的部分，當作這段程式的 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，只要專注在會影響效能的那段就好。