2021/07/04 資訊之芽 熊育霆
Outline
台大資工系有一門大一必修,課名就是「資料結構與演算法」,我們花了一整個學期、每週至少三小時在學這些東西。
另一門大二必修叫做「演算法設計與分析」,一樣每週至少三小時在學這些東西。
聽一聽有興趣的同學可以參考隔壁算法班的課程。
我們通常會用以下兩個指標來衡量一個演算法有多「好」
今天的課程主要會先著重在「時間」部份
但是直接測量一個演算法的執行時間通常不是很實際的作法(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符號
舉個例子,假設一個演算法的執行時間(或者所需步驟數)可以用
\[T(n) = 2n^2 + n + 10\]
表示,其中\(n\)為輸入的大小
\[T(n) = 2n^2 + n + 10\]
當\(n\)夠大的時候,除了\(2n^2\)以外的其他項的影響可以忽略
這時我們會寫作\(T(n) = O(n^2)\)
沒那麼精確地說,使用大O符號時,我們會把影響比較小的項以及係數省略
更多例子
在計算機科學中,可以把大O符號理解成「描述一個函數在\(n\)很大時的行為」
因此我們不會說「當\(n<100\)時\(T(n) = O(n^2)\)」或是「因為可觀測的宇宙原子數量只有\(10^{70}\)這麼多,所以所有演算法都是\(O(1)\),實作為王」等等
有興趣深入了解的可以問問一些資訊圈的同學「月球先生之亂」的故事
大O符號有精確的數學定義,其中兩個等價定義如下,長到塞不下
\[f(n) = O(g(n)) \iff \limsup_{n \to \infty} |\frac{f(n)}{g(n)}| < \infty\]
\[f(n) = O(g(n)) \iff \exists c > 0, n_0 > 0\ \text{such that} \ \forall n > n_0, |f(n)| \leq |cg(n)|\]
用人話來說就是對所有夠大的\(n\),\(f(n)\)的大小會被\(g(n)\)的某個常數倍壓住
假設你把備審資料放在某個置物櫃裡面,但你忘記它在哪個置物櫃中,因此你需要一一檢查每個置物櫃。假設有\(n\)個置物櫃,請問最壞的狀況下,你需要花多少時間才能找到備審資料?
方法:依序檢查
for i in range(n): if data_is_in(lockers[i]): return i
最壞的狀況:東西在最後一個你檢查的置物櫃
因此最壞需要花\(n\)秒
我們會說這個方法需要花費\(O(n)\)時間
答案在下一頁
A: 都是\(O(n)\)時間(線性時間)
唐鳳用他的腦波控制超能力來幫助你了,他可以馬上知道你的備審資料在哪個櫃子裡。
他每次使用這個超能力時需要10秒鐘充能。用大O符號表示的話,這個方法會花費\(O(?)\)時間?
A: \(O(1)\) 常數時間,因為跟輸入大小\(n\)無關
假設現在這\(n\)個櫃子上鎖了,每個櫃子都有一把對應的鑰匙,這\(n\)把鑰匙全都混在一個袋子裡,你不知道哪把鑰匙對應到的櫃子是哪一個。
你每次只能用一把鑰匙去試一個櫃子,假設這個過程需要一秒鐘。打開櫃子的過程時間可以忽略不計。
以下給出幾個python指令相對應的時間複雜度 (忽略位元數量)
接下來會介紹一些有趣的演算法
給定一個排序好的數列,決定給定目標是否存在以及其位置
Ex. [1, 2, 3, 5, 8, 13]
,5有沒有在這裡面?
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
總結來說,時間複雜度為\(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)\)
print('嗨呀哭 摸都嗨呀哭')
快速排序法使用分治法(divide & conquer)把數列分成較小的兩個子數列,然後遞迴排序兩個子數列
人話詳細作法在下一頁
快速排序步驟
對基準左邊的數列和基準右邊的數列做快速排序
這就是分治法的精神:把問題分割成多個比較小的子問題解決。如果這個子問題還不夠小,就繼續切下去。
在這個演算法來說,當\(n \leq 1\)時可以直接解決。
快速排序的時間複雜度分析有點複雜,因此我會略過
不精確地說,期望上每次挑選基準會把數列分成大小差不多的兩塊,因此期望上加總起來會需要做\(\log n\)次\(n\)個比較 (這裡省略了非常多細節)。
結論上,平均上是\(O(n \log n)\) (更精確來講是\(\Theta(n \log n)\))
最糟情況會是\(O(n^2)\) (why?)
如果你還是沒有懂這個作法,可以看他們跳舞
用於判斷一個鍊結串列(linked-list)是否有環
這就叫做一個有環的linked-list
演算法:
鍊結串列無環的情況顯然(因為兔子一定走得到終點)
以下假設鍊結串列有環
鍊結串列無環的情況比較簡單,兔子走到終點大略需要做\(N/2\)次步驟2. ,因此是\(O(N)\)
鍊結串列有環的狀況下,烏龜進到環裡面以後最多只能再走一圈,因此時間複雜度為\(O(N)\)