# Algorithm basics 初探演算法 Made by Yu-Chi Lai ---- ## Review 就...複習幾個前幾堂課講過的..觀念 ---- ### Q1 在 Linux 中，當前資料夾中有個資料夾叫做folderuwu，我如果打出: ```!= sudo rm -f folderuwu cd folderuwu ``` 會有什麼效果? ---- ### Q2 ```python= arr1 = [1, 3, 5, 7, 9] arr2 = [2**x for x in arr1] for i in arr2: print(i, end = ' ') ``` 會輸出什麼？ ---- ### Q3 ```python= func = lambda x, y, z : (x**y) % z print(func(2,5,10)) ``` 會輸出什麼？ ---- ### Q4 是非題: ( ) 網站開發中，前端與後端的差別只在於使用的程式語言不同。前者使用 HTML、CSS、Javascript，後者使用 SQL、Python ---- ### Q5 ```python= st = {1} for i in range(5): st.add(i) print(st) # 0, 1, 2, 3, 4 st.add(3) print(st) # 0, 1, 2, 3, 4 ``` st 代表著之前介紹過的什麼容器(Container)？ --- ## Intro 什麼是演算法？能吃嗎？ ---- > 由有限步驟所構成的集合，可以用於解決某一個特定的問題。 ---- ### E.G. 做珍珠奶茶 1. 混合牛奶與紅茶 2. 將珍珠加入 3. 依照客人需求加入冰塊 4. 封裝並搖勻 => 這就是製作一杯珍珠奶茶的演算法 ---- ### In Computer Science... 我們透過設計一連串的指令、動作，讓電腦去執行，以便協助我們解決一些特定問題。  ---- ### Coming soon... #### 什麼是資料結構 (Data structure)? + 在計算機科學中用來**儲存、組織和管理數據**的方法 + Array、Queue、Stack、Tree...etc --- ## Complexity (複雜度) 需要很多數學，可能沒辦法講太深 ---- ### 要怎麼評估一個程式好不好？ + <!-- .element: class="fragment" data-fragment-index="1" -->程式碼夠簡潔？ + <!-- .element: class="fragment" data-fragment-index="2" -->跑得夠快？ + <!-- .element: class="fragment" data-fragment-index="3" -->用到的記憶體多不多？ + <!-- .element: class="fragment" data-fragment-index="4" -->其實都沒有錯！ ---- ### 新概念：複雜度 1. 時間複雜度 (Time Complexity)： 執行演算法時須花費的時間。 2. 空間複雜度 (Space Complexity)： 執行演算法時須花費的記憶體空間。 ---- ### 數數: 執行幾次? ```python! n = int(input()) arr = [] for i in range(n): arr.append(i) ``` + <!-- .element: class="fragment" data-fragment-index="1" -->n 次 ---- ### 數數: 執行幾次? ```python! n = int(input()) m = int(input()) arr = [] for i in range(n): for j in range(m): arr.append(i + j) ``` + <!-- .element: class="fragment" data-fragment-index="1" -->n*m 次 ---- ### 數數: 執行幾次? ```python! n = int(input()) while(n != 0): n /= 2 ``` + $\log{n}$ 次 (以2為底) ---- ### 題外話: [對數](https://zh.wikipedia.org/zh-tw/%E5%AF%B9%E6%95%B0) 簡單來說，指對數的概念有點相反: $2^x=8，則\ x=\log^8_2=3$ 如果我們今天寫出 $\log^b_a$，要求的是 $a$ 的**幾次方**會等於 $b$！ :::success 在這裡 $a$ 稱作底數，$b$ 稱作真數 ::: ---- ### Big-O notation + **正式定義**：$f(n)=O(g(n))$，若且唯若存在正實數 $c$、正實數 $n₀$，對於所有的 $n≥n₀$，可滿足 $0 ≤ f(n) ≤ c·g(n)$。 + <!-- .element: class="fragment" data-fragment-index="1" -->三小 + <!-- .element: class="fragment" data-fragment-index="2" -->看不懂沒關係，我們可以把 Big-O 這個複雜度的指標，看作運算時間的成長速度。所以 big-O 裡面的值越小，代表時間複雜度越好！ ---- ### 什麼意思？  當 n 越來越大，$2^n、n!$ 的值會遠遠超過 $n、\log{n}$ ---- 假設某一段程式所運算的**步驟數**可以表示成: $T(n)=2n^2+3n+1$ $n$ 為輸入的大小 + 當 n 越來越大時，後面的 $3n+1$ 將無足輕重 (但也並非毫無意義) ---- 這時我們會把該程式的時間複雜度寫作: $T(n)=O(n^2)$ 換言之，使用 big O notation 時，我們會把影響比較小的項以及係數省略 ---- ### More examples + $T(n)=n+5\Rightarrow T(n)=O(n)$ + linear time 線性時間 + $T(n)=n^2+5n\Rightarrow T(n)=O(n^2)$ + quadratic time 平方時間 + $T(n)=48763\Rightarrow T(n)=O(1)$ + constant time 常數時間 + $T(n)=2^n\Rightarrow T(n)=O(2^n)$ + exponential time 指數時間 --- ## Sorting 常見的排序算法 ---- ### 太多了 + 泡沫排序 (Bubble sort) + 插入排序 (Insertion sort) + 快速排序 (Quick sort) + 合併排序 (Merge sort) + ... + [學習資源](https://ithelp.ithome.com.tw/m/articles/10326482) --- ## Binary Search 二分搜尋法 ---- ### 猜數字 假設我從 1~100 選 1 個數字作為答案。你要怎麼猜才可以最有效率地猜到？ ---- ```python= ans = int(input()) left = 1 right = 100 while left <= right: mid = (left + right) // 2 if mid == ans: print(f'The answer is {mid}') elif mid > ans: mid -= 1 else: mid += 1 ``` --- ## Dynamic Programming 動態規劃 ---- ### What is DP? 是透過把原問題分解為相對簡單的子問題的方式，來求解複雜問題的方法。 ---- ### 費氏數列 ```py= def fact(n): if n == 0 || n == 1: return 1 else: return fact(n-1) + fact(n-2) ``` 老實說這樣寫很慢 ----  我們重複計算了fib(3)、fib(4) ... ---- 我們可以將已經算過ㄉ部份，儲存在list裡面！ ```pyth= f = [0 for i in range(100)] def fibo(n): if f[n]: return f[n] if n <= 1: return 1 f[n] = fibo(n-1) + fibo(n-2) return f[n] n = 45 for i in range(n+1): print(fibo(i), end=' ') print() ``` --- ## 學習資源 How to 變強 ---- ### 題目 + CSES + Codeforces + TIOJ ---- ### 社團/活動 + 成功電研 + SITCON + AIS3 + 資訊之芽