複雜度&演算法

# 複雜度&演算法資訊之芽北區py班 yjrubixcube --- ## 時間/空間複雜度簡單來說就是你的程式有快，或是需要多少空間今天主要講時間的部分 ---- 如果寫一個算list總和的程式 ```python= for i in l: sum += i print(sum) ``` 這個程式會跑多久?? ---- |code|次數|時間| |-|-|-| |next(i)|n-1|$t_1$ |sum += i | n|$t_2$ |print(sum)|1|$t_3$ n 是 list 的長度總共耗時就是每一個code的時間加總 $(n-1)t_1+n(t_2)+t_3$ ---- 但是每個人的電腦不一樣，需要花的時間也不一樣所以要一個能夠不受電腦影響，也能夠衡量演算法效率的方法 --- ## 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$ 就可以說 $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\implies f(n)=O(3^n)$ - 指數時間 exponential time - $f(n)=9487\implies f(n)=O(1)$ - 常數時間 constant time ---- ### 食用(?)的:chestnut: ---- 假設你去超市買:chestnut:，但是超市沒有標示東西在哪個架子上，所以你只能一個一個慢慢找架子上有沒有:chestnut:。超市總共有n個架子，最壞的情況會需要找幾次? ---- 方法：從第一個架子依序往後找 ```python= for i in range(n): if found_chestnut[aisle[i]]: return i ``` ---- 假設你找一個架子需要1分鐘最壞的情況：:chestnut:在最後一架子最壞總共要找n個架子，花n分鐘這個方法花的時間是$O(n)$ ---- 假設你媽找一個架子只需要0.1分鐘最壞的情況：:chestnut:在最後一架子最壞總共要找n個架子，花0.1n分鐘這個方法花$O(?)$時間 還是$O(n)$時間 ---- 假設你阿嬤找一個架子要花5分鐘，開始找之前會花30分鐘把你餵飽最壞的情況：:chestnut:在最後一架子最壞總共要找n個架子，花5n+30分鐘這個方法花$O(?)$時間 還是$O(n)$時間 ---- 假設超商怕有人偷東西所以每個架子都鎖起來，而且鑰匙全部丟在同一個袋子裡面你一次只能試一把鑰匙能不能開一個架子，試一次要花0.1分鐘其他時間可以忽略 ---- 最壞的情況：每個架子試n次鑰匙，所以一個架子要花0.1n分鐘 :chestnut:在第n個架子，總共是$n*0.1n=0.1n^2$分鐘這個方法花$O(?)$時間 是$O(n^2)$時間 ---- 假設你跑去問超市店員，店員用電腦查後直接告訴你:chestnut:在哪但是電腦開機+查詢需要5分鐘這個方法花$O(?)$時間 是$O(1)$時間 因為不管架子有多少都是5分鐘 --- ## 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= for i in l: sum += i print(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)