台大資工系有一門大一必修，課名就是「資料結構與演算法」，我們花了一整個學期、每週至少三小時在學這些東西。
另一門大二必修叫做「演算法設計與分析」，一樣每週至少三小時在學這些東西。
聽一聽有興趣的同學可以參考隔壁算法班的課程。

我們通常會用以下兩個指標來衡量一個演算法有多「好」

• 使用的時間
• 使用的空間

今天的課程主要會先著重在「時間」部份

但是直接測量一個演算法的執行時間通常不是很實際的作法(Why?)

def some_func(a, b):
    print(a)
    print(b)
    c = a + b
    return c

假設我們這樣拆解，每一行的執行時間可能會是這樣

def some_func(a, b):
    print(a) # cost: c1 sec
    print(b) # cost: c2 sec
    c = a + b # cost: c3 sec
    return c # cost: c4 sec

在另一台電腦上跑的時間可能會不一樣

def some_func(a, b):
    print(a) # cost: d1 sec
    print(b) # cost: d2 sec
    c = a + b # cost: d3 sec
    return c # cost: d4 sec

會影響一支程式執行時間的因素可能有：

• 輸入（ (a, b) = (1, 1) 還是 (a, b) = (10000, 10000)?）
• 機器（計算能力）
• 環境（溫度、濕度）
• 其他…

即使如此，我們還是希望能夠衡量一個演算法的執行效率

因此需要一個方法，能夠衡量演算法的執行效率，且不被以上因素影響

漸近符號在分析演算法效率上非常有用。以下是漸近符號家族

• \(O(g(n))\) - 今天只會講這個，其他有興趣可以再來跟我討論
• \(\Omega(g(n))\)
• \(\Theta(g(n))\)
• \(o(g(n))\)
• \(\omega(g(n))\)

\(O(g(n))\) - Big-Oh Notation

中文唸作大O符號

舉個例子，假設一個演算法的執行時間（或者所需步驟數）可以用

\[T(n) = 2n^2 + n + 10\]

表示，其中\(n\)為輸入的大小

\[T(n) = 2n^2 + n + 10\]

當\(n\)夠大的時候，除了\(2n^2\)以外的其他項的影響可以忽略

• \(n = 10, T(n) = 200 + 10 + 10 = 220\)
• \(n = 100, T(n) = 20000 + 100 + 10 = 20110 \approx 2 \cdot 100^2\)
• \(n = 1000, T(n) = 2000000 + 1000 + 10 = 2001010 \approx 2 \cdot 1000^2\)

這時我們會寫作\(T(n) = O(n^2)\)

沒那麼精確地說，使用大O符號時，我們會把影響比較小的項以及係數省略

更多例子

• \(T(n) = n \implies T(n) = O(n)\)
  • linear time 線性時間
• \(T(n) = 100n^2 + 5 + \frac{1}{n} \implies T(n) = O(n^2)\)
  • quadratic time 二次時間（？）
• \(T(n) = 8763 \implies T(n) = O(1)\)
  • constant time 常數時間
• \(T(n) = 2^n \implies T(n) = O(2^n)\)
  • exponential time 指數時間

https://blog.yangjerry.tw/2019/01/31/fibonacci-is-bigO1/

用人話來說就是對所有夠大的\(n\)，\(f(n)\)的大小會被\(g(n)\)的某個常數倍壓住

假設你把備審資料放在某個置物櫃裡面，但你忘記它在哪個置物櫃中，因此你需要一一檢查每個置物櫃。假設有\(n\)個置物櫃，請問最壞的狀況下，你需要花多少時間才能找到備審資料？

• 假設你檢查一個置物櫃需要一秒鐘

方法：依序檢查

for i in range(n):
    if data_is_in(lockers[i]):
        return i

最壞的狀況：東西在最後一個你檢查的置物櫃

因此最壞需要花\(n\)秒

我們會說這個方法需要花費\(O(n)\)時間

• Q1: 如果今天是你阿嬤幫你翻櫃子，每翻一個櫃子需要花費10秒鐘，而且她會在開始翻櫃子以前花5分鐘確認你吃飽了沒。在這個情況下最壞需要花\(10n+300\)秒，用大O符號表示的話，這個方法會花費\(O(?)\)時間？

• Q2: 翻櫃子世界紀錄保持人來幫你檢查櫃子，他每翻一個櫃子只需要0.1秒，用大O符號表示的話，這個方法會花費\(O(?)\)時間？

答案在下一頁

A: 都是\(O(n)\)時間（線性時間）

唐鳳用他的腦波控制超能力來幫助你了，他可以馬上知道你的備審資料在哪個櫃子裡。
他每次使用這個超能力時需要10秒鐘充能。用大O符號表示的話，這個方法會花費\(O(?)\)時間？

A: \(O(1)\) 常數時間，因為跟輸入大小\(n\)無關

• 每個櫃子最爛會試到\(n\)把鑰匙，所以每開一個櫃子需要\(n\)秒
• 總共有\(n\)個櫃子，這樣加起來總共需要\(n^2\)秒
• 用大O符號來表示，我們會需要\(O(n^2)\)時間

• 加減乘除 - \(O(1)\)
• 存取一個list的某個元素 - \(O(1)\)
• 遍歷一個大小為\(n\)的list - \(O(n)\)
• 在大小為\(n\)的list位置0的地方做插入操作 - \(O(n)\)
• 排序一個大小為\(n\)的list - \(O(n \log n)\)
• 存取一個dictionary某個key對應到的value - \(O(1)\) (What?)

1. 一開始先從中間切一刀
2. 看中間那個數是否是我們要的
3. 如果是，那就做完了
4. 如果中間那個數比我們要的小，就往右邊再切一刀並回到2.
5. 如果中間那個數比我們要的大，就往左邊再切一刀並回到2.
6. 切到最後還是沒找到，那我們要的數字不在這個數列裡面

def binary_search(arr, left, right, hkey):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == hkey:
            return mid
        elif arr[mid] < hkey:
            left = mid + 1
        elif arr[mid] > hkey:
            right = mid - 1
    return -1

時間複雜度分析

• 我們可以去計算總共要切幾刀
• 每次切一刀下去會淘汰掉這個數列一半的元素。
• 也就是說，假設一開始數列大小為\(n\)，切完一刀後只會剩下\(n/2\)這麼多需要檢查。
• 只剩下一個元素時直接檢查就好。
• 因此大約需要切\(\log n\)這麼多刀

總結來說，時間複雜度為\(O(\log n)\)

def bubble_sorted(l):
    n = len(l)
    for i in range(n):
        for j in range(n - i - 1):
            if l[j] > l[j + 1]:
                l[j], l[j + 1] = l[j + 1], l[j]

簡單算一下可以發現中間的nested for-loop總共會跑
\[ 1 + 2 + ... + (n-1) = n(n-1)/2\]
這麼多次，因此時間複雜度為\(O(n^2)\)

快速排序法使用分治法(divide & conquer)把數列分成較小的兩個子數列，然後遞迴排序兩個子數列

人話詳細作法在下一頁

快速排序步驟

1. 如果數列長度\(n \leq 1\)，那這個數列已經是排序好的狀態了，直接return
2. 從數列中隨便挑選一個數當作基準(pivot)
3. 依序把數列中其他數字與基準做比較，比基準小的放在左邊，比基準大或相等的放右邊
4. 對基準左邊的數列和基準右邊的數列做快速排序

對基準左邊的數列和基準右邊的數列做快速排序

這就是分治法的精神：把問題分割成多個比較小的子問題解決。如果這個子問題還不夠小，就繼續切下去。
在這個演算法來說，當\(n \leq 1\)時可以直接解決。

時間複雜度

快速排序的時間複雜度分析有點複雜，因此我會略過

不精確地說，期望上每次挑選基準會把數列分成大小差不多的兩塊，因此期望上加總起來會需要做\(\log n\)次\(n\)個比較 (這裡省略了非常多細節)。

結論上，平均上是\(O(n \log n)\) (更精確來講是\(\Theta(n \log n)\))
最糟情況會是\(O(n^2)\) (why?)

維基百科程式碼

如果你還是沒有懂這個作法，可以看他們跳舞

• Floyd Cycle Detection Algorithm
• Floyd's Tortoise and Hare Algorithm

What is a linked-list?

這就叫做一個有環的linked-list

演算法：

1. 烏龜和兔子一開始都在起點
2. 烏龜走一步，兔子走兩步，然後做以下檢查：
   • 如果兔子抵達終點，則此鍊結串列無環
   • 如果兔子和烏龜相遇，則此鍊結串列有環
   • 如果都不是，再做一次2.

正確性分析

鍊結串列無環的情況顯然（因為兔子一定走得到終點）
以下假設鍊結串列有環

• 假設鍊結串列長度為\(N\)，環的大小是\(C>0\)
• 每做一次步驟2. 烏龜和兔子的距離會增加1
• 當烏龜和兔子都進到環裡以後，最多再走\(C\)次步驟2.（非常粗略的估計），他們的距離總會變成\(C\)的某個整數倍，這時烏龜和兔子就會相遇

時間複雜度分析

鍊結串列無環的情況比較簡單，兔子走到終點大略需要做\(N/2\)次步驟2. ，因此是\(O(N)\)
鍊結串列有環的狀況下，烏龜進到環裡面以後最多只能再走一圈，因此時間複雜度為\(O(N)\)