複雜度&演算法 2024

# 複雜度&演算法 2024 資訊之芽北區py班 yjrubixcube ---- :syringe: 這堂( C12H22O11)課可能會聽不懂有任何問題都可以問我或是後面講師 --- ## 時間/空間複雜度簡單來說就是你的程式有快，或是需要多少空間今天主要講時間的部分 ---- 如果寫一個算list總和的程式 ```python= list_sum = 0 for i in l: list_sum += i print(list_sum) ``` 這個程式會跑多久?? ---- |code|次數|時間| |-|-|-| |next(i)|n-1|$t_1$ |list_sum += i | n|$t_2$ |print(list_sum)|1|$t_3$ n 是 list 的長度總共耗時就是每一段code的時間加總 $(n-1)t_1+n(t_2)+t_3$ ---- 可能會影響執行時間的因素 - 硬體(電腦計算能力、型號) - 環境(溫度、濕度、[被宇宙射線打到](https://www.youtube.com/watch?v=AaZ_RSt0KP8)) - 輸入(`[1, 2, 3]` vs `[10000, 20000, 30000]`) - 其他所以要一個能夠不受外在影響，也能夠衡量演算法效率的方法 --- ## Big O notation $O(g(n))$ ---- 定義 $f(n)=O(g(n))\iff$ $\exists c>0,x_0>0$ such that $\forall x>x_0,|f(x)|\leq c*g(x)$ 簡單翻譯一下就是當n足夠大的時候 $f(n)$會被$g(n)$的常數倍壓住 ---- 通常會取影響最大的項(次方數最高、指數底數最大) 而且會把常數倍數拿掉 ---- 舉個:chestnut:比較好懂 $f(n)=3n^2+5n+6$ $n=10, f(n)=300+50+6=356$ $n=100, f(n)=30000+500+6\approx30000$ $n=1000, f(n)=3*10^6+5*10^3+6\approx3*10^6$ 當$n$夠大的時候，$3n^2$的影響會超過其他項就可以說 $f(n)=O(n^2)$ ---- 其他:chestnut: - $f(n)=n+100\implies f(n)=O(n)$ - 線性時間 linear time - $f(n)=3n^2+5n+6\implies f(n)=O(n^2)$ - 平方時間 quadratic time - $f(n)=3^n+n^2+2^n\implies f(n)=O(3^n)$ - 指數時間 exponential time - $f(n)=9527\implies f(n)=O(1)$ - 常數時間 constant time ---- 我們也可以說 $f(n)=n+100\implies f(n)=O(n^{87})$ 但是通常會求最小的 $g(n)$ ---- 除了$O$以外，還有其他符號($o, \Theta, \omega, \Omega$...) 有(ㄒㄧㄤˇ)興(ㄅㄨˋ)趣(ㄎㄞ)的可以自己去[研究](https://www.geeksforgeeks.org/types-of-asymptotic-notations-in-complexity-analysis-of-algorithms/) ---- ### 食用(?)的:chestnut: ---- 假設你把:chestnut:放在某個置物櫃裡面，但是你忘記是哪個置物櫃，所以你只能一個一個打開看。假設有$n$個置物櫃，最壞的情況需要找幾次？ ---- 方法：從第一個櫃子依序往後找 ```python= for i in range(n): if chestnut_is_in(locker[i]): return i ``` ---- 假設你找一個置物櫃需要5秒最壞的情況：:chestnut:在最後一個置物櫃最壞總共要找n個置物櫃，花5n秒這個方法花的時間是$O(n)$ ---- 假設你媽找一個置物櫃只需要1秒最壞的情況：:chestnut:在最後一個置物櫃最壞總共要找n個架子，花n秒這個方法花$O(?)$時間 還是$O(n)$時間 ---- 假設你阿嬤找一個置物櫃要花10秒，開始找之前會花30分鐘把你餵飽最壞的情況：:chestnut:在最後一架子最壞總共要找n個架子，花10n+30*60秒這個方法花$O(?)$時間 還是$O(n)$時間 ---- 假設:chestnut:溝通師在跟你的:chestnut:溝通後可以馬上知道:chestnut:在哪裡，但是每次溝通需要花1小時這個方法花$O(?)$時間 是$O(1)$時間 因為不管置物櫃有多少都是1小時 ---- 假設每個置物櫃都上鎖了，而且鑰匙全部丟在同一個袋子裡面你一次只能試一把鑰匙能不能開一個置物櫃，試一次要花1秒其他時間可以忽略 ---- 最壞的情況：每個置物櫃試n次鑰匙，所以一個置物櫃要花n秒 :chestnut:在第n個置物櫃，總共是$n*n=n^2$秒這個方法花$O(?)$時間 是$O(n^2)$時間 --- ## python 的複雜度 ---- python 常見的一些指令的複雜度 - 加減乘除 $O(1)$ - 存取list裡面的一個元素 $O(1)$ - traverse一個list $O(n)$ - append/pop list的最後面 $O(1)$ - insert/delete list最前面的元素 $O(n)$ - sort一個list $O(n\log n)$ - 存取dict某個key對應的value $O(1)$(?) ---- 回到最一開始的例子 ```python= list_sum = 0 for i in l: list_sum += i print(list_sum) ``` 這個程式是$O(?)$ $O(n)，因為需要traverse所有元素$ ---- ```python= sum = 0 for i in range(n): sum += i if sum > 1000: break ``` 這個程式是$O(?)$ $O(1)$ ---- ```python= for i in range(len(l)): m = min(l) l[i] += m ``` 這個程式是$O(?)$ $O(n^2)$ --- ## 演算法介紹 ---- ### 甚麼是演算法維基：演算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來翻譯：解決某類問題的步驟 ---- 要怎麼把大象塞到冰箱裡 1. 把冰箱打開 2. 把裡面的東西拿出來 3. 把大象放進去 4. 把冰箱關起來 --- ## 簡單演算法介紹-二分搜尋法 ---- ### 二分搜尋法給定一個排序好的list，問x在list的哪裡例如：5 有沒有在`[1, 3, 4, 7, 11, 18, 29]`裡面 ---- 1. 把list切一半，取中間的元素`l[i]` 2. 把`l[i]`跟x做比較 1. `x == l[i]`：找到了，收工 2. `x < l[i]`：x可能在左半邊 3. `x > l[i]`：x可能在右半邊 3. 重複1 2，而且只對左/右半邊去做搜尋 4. 如果切完了還沒找到，代表x不在list裡面 ---- 找23 ![](https://i.imgur.com/A3fyvNQ.png) ---- ```python= def binary_search(arr, target): left, right = 0, len(arr)-1 while left <= right: mid = left + (right - left)//2 if arr[mid] == target: return mid if arr[mid] > target: right = mid -1 else: left = mid + 1 return -1 ``` ---- 時間複雜度每一次切都會把長度除以2 原本長度為n，切一次變n/2 如果長度只有1，可以直接檢查是不是x 總共大概會切$\log n$次 時間複雜度：$O(\log n)$ --- ## 簡單演算法介紹-泡泡排序 ---- 每次迴圈都把最大的元素"浮"到後面 ---- ![](https://i.imgur.com/2VKdEN0.png) ---- 練習時間試試看自己寫bubble sort ---- :rice:解 ```python= def bubble_sort(arr): l = len(arr) for i in range(l): for j in range(l-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] ``` ---- 時間複雜度算一下可以算出最裡面的判斷會跑$n(n-1)/2$次 時間複雜度：$O(n^2)$ --- ## 沒那麼簡單演算法介紹-合併排序 merge sort ---- 使用分治法(divide and conquer) 1. 把list分兩半 2. 每一半分別排序(還是用merge sort) 3. 兩半合併 ---- ![](https://i.imgur.com/55JhQdn.png) ---- ```python= def merge(left, right): output = [] l, r = 0, 0 len_l, len_r = len(left), len(right) while l<len_l and r<len_r: if left[l] <= right[r]: output.append(left[l]) l+=1 else: output.append(right[r]) r+=1 if l<len_l: output.extend(left[l:]) if r<len_r: output.extend(right[r:]) return output ``` ---- ```python= def merge_sort(arr): l = len(arr) if l <= 1: return arr left, right = arr[:l//2], arr[l//2:] left = merge_sort(left) right = merge_sort(right) return merge(left, right) ``` ---- 時間複雜度 `merge`的部分是O(n) 總共合併$O(\log n)$次可以算出$T(n)=O(n\log n)$ 這是非常簡略的算法，酷酷的東西放延伸閱讀 --- ## 簡單(?)演算法介紹-計數排序 counting sort ---- 剛剛前面提到的sort都是比較排序(comparison based) 比較排序的時間下界是$n\log n$ 如果要更快的話，要用空間換時間 ---- ### counting sort - 只能sort整數 - 適合最大最小值差距不大的數據 ---- 1. 開一個新的陣列，用來記每個元素出現幾次 2. traverse原本的陣列，就可以把元素sort到該出現的位置 ---- ![](https://i.imgur.com/sHRA4tX.png) ---- ```python= def counting_sort(arr): a_min = min(arr) a_max = max(arr) count = [0 for _ in range(a_max-a_min+1)] for i in arr: count[i-a_min] += 1 for i in range(len(count)): if i == 0: continue count[i] += count[i-1] output = [0 for _ in range(len(arr))] for i in arr: output[count[i-a_min]-1] = i count[i-a_min] -= 1 return output ``` ---- 時間複雜度可以看出counting sort只有做traverse，沒有遞迴。 traverse `arr`要花$O(n)$時間 traverse `count`要花$O(k)$時間 ($k=$最大最小值的差) 總共的時間複雜度是$O(n+k)$ ---- 空間複雜度因為需要多開一個`count`的陣列，加上原本要排序陣列的，總共需要的空間是$O(n+k)$ --- ## 延伸閱讀 - [python用timsort](https://en.wikipedia.org/wiki/Timsort) - [怎麼用遞迴算time complexity](https://www.geeksforgeeks.org/how-to-solve-time-complexity-recurrence-relations-using-recursion-tree-method/) - [怎麼直接算complexity](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)) - 看演算法跳舞[AlgoRythmics](https://www.youtube.com/user/AlgoRythmics/videos) - [sorting音樂](https://youtu.be/LOZTuMds3LM) - [python的time complexity](https://wiki.python.org/moin/TimeComplexity)