# 演算法概論 by:何煦 --- ## 大綱 ---- 1. **演算法** 2. **複雜度** 2. **枚舉法** 3. **二分搜** 4. **貪心法** 5. **結語** --- ## 1.演算法(algorithm) ---- 有一位偉人說過: 程式設計 = 資料結構 + **演算法** by colin : 偉人是Pascal語言創建者 Niklaus Wirth ---- 演算法是什麼? ---- 演算法是一系列用來解決問題具體的步驟或方法 ---- 例如說: 你想去圖書館找一本《$813$之謎》  ---- 那麼你可以去圖書館把每一本書都找一遍 或著你可以先查它的索書號，去找到 文學類的書架，在從那些書架上找 ---- 這兩種方法都是找書的**演算法** ---- 問題來了: 哪種方法比較好? 為什麼? --- ## 2.複雜度(complexity) ---- 要如何分析演算法好壞? ---- 看它的執行的時間和使用的記憶體量多寡 ---- 也就是**時間複雜度**和**空間複雜度** ---- ### 時間複雜度: ---- 我們通常會假設程式每行執行時間一樣 然後根據**輸入的數**和**執行行數**的關係來計算 ---- 也就是假設輸入了一個數$n$ 看這個程式會跑$n$行還是$n^2$行之類的 來當作時間複雜度 ---- 把時間複雜度乘上每行執行時間 就可以知道這個程式大概要跑多久了 ---- 但複雜一點的程式可能算出來 複雜度是:$3𝑛^3 + 5𝑛^2 + 10𝑛 + 3$ 每個都要列出來很麻煩 ---- 所以常會用**Big-O**符號來表示複雜度 **Big-O**符號可以忽略影響不大的首項係數和低次項 例如:$3𝑛^3 + 5𝑛^2 + 10𝑛 + 3 = O(n^3)$ ---- ### 空間複雜度: ---- 跟時間複雜度很像 根據**輸入的數**和**使用的記憶體量**的關係來計算 ---- 看你用幾個變數、開多大的陣列之類的 ---- 一樣也會用**Big-O**符號來表示複雜度 例如:開一個長度為$n$的陣列，空間複雜度就是$O(n)$ --- ## 3.枚舉法(Enumerate) ---- 又稱窮舉法，基本思想是通過列舉所有的可能性，然後在其中找到符合條件的最佳解。 ---- 優點是很好想、不容易漏掉東西 缺點是效率不高、有些問題可能性有無限多個 ---- 應用:判斷一個自然數$n$是否為質數 ---- 質數定義: 大於1的自然數中，除了1和該數本身，無其他因數的數 ---- 所以可以枚舉$2$ ~ $n-1$所有的數 檢查$n$是否被整除，若完全沒有那$n$為質數 ---- code: ```C++= #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; //輸入n bool ans=true; if (n==1) ans=false; for (int i=2;i<=n-1;i++) if (n%i==0) ans=false; ans ? cout << "Yes\n" : cout << "No\n"; } ``` ---- 剪枝: 減少不必要的枚舉 ---- 回到剛剛那題，若$n$不是質數，必存在兩個整數 相乘等於$n$，較小的數則必不大於$\sqrt n$ 所以可以不必枚舉到比$\sqrt n$大的數 ---- code: ``` #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; bool ans=true; if (n==1) ans=false; for (int i=2;i<=floor(sqrt(n));i++)//sqrt()求根號 if (n%i==0) ans=false; ans ? cout << "Yes\n" : cout << "No\n"; } ``` --- ## 4.二分搜(binary search) ---- 就是每次剪掉一半可能性的枚舉 可用在有單調性的問題(非嚴格遞增/減) ---- 丟雞蛋問題: 給你一種超硬的雞蛋很多顆，在一個100層的大樓 測試雞蛋最低在哪一層會開始破掉 ---- 如果從第一層開始去一層一層慢慢砸效率太低 最多會算到$100$次 ---- 在經過精密的計算後發現雞蛋破的情況長這樣: 100破了 99破了 ⁝ 32破了 31破了 30沒破 ⁝ 02沒破 01沒破 ---- 所以當你在第$n$層丟一顆雞蛋 如果它沒破，代表$1$ ~ $n$都是沒破 反之它就是破了，那$n$ ~ $100$都是破了 ---- 那每次都從一半檢查，就可以排除一半可能性 直到找到沒破和破的交界處 ---- 大概長這樣:  ---- 應用:在遞增序列中找出某數$n$的位置 例如:在1, 3, 4, 6, 7, 8, 10, 13, 14 找到4在第幾個 ---- 把小於4的數看成沒破的蛋 找到第一個破的蛋，相當於大於等於$4$的數 如果是4就回傳位置，否則回傳找不到 ---- 示意圖:  作者:Tushe2000, 來源:wikipedia ---- code: ```C++= int binary_search(int l,int r,int tar,int a[]) { int mid=l+(r-l)/2; while (l<r) { if (tar>a[mid]) l=mid+1; else r=mid-1; mid=l+(r-l)/2; } return a[l]==tar ? l : -1; } ``` --- ## 5.貪心法(greedy) ---- 在每一步選擇中都不考慮後面結果 採取在當前最佳(即最有利)的選擇 ---- 就像先玩樂再讀書 🎮 → 📖 是很一種直覺的方法 ---- 例子: 假設你去買一杯飲料，然後付給店員一張千元鈔。店員找你越少鈔票和零錢他越輕鬆，他要如何找錢? ---- 依照生活經驗你當然也知道要從面額最大的開始拿 因為所有小面額的錢都是大面額的因數 任何大面額的錢換成小面額的錢都不會更優 ---- code: ```C++= #include <bits/stdc++.h> using namespace std; int main() { int n,ans=0; cin >> n; int money[]={1000,500,100,50,10,5,1}; for (int i=0;i<7;i++) { ans+=(n/money[i]);//計算目前最大面額可用幾張 n=n%money[i];//扣掉已經花的錢 } cout << ans <<'\n'; } ``` ---- 貪心法雖然很直覺，但是需要嚴謹的證明避免出錯 因為本人資質不佳不會寫，只好拿別人的證明示範 ----  ----  --- ## 6.結語(conclusion) ---- 演算法的內容非常非常多 今天時間有限只能挑一點點講 ---- 如果對演算法有興趣的話可以: * 上網或是借書自學 * 去上一些課程(像是資訊之芽) * 加入學校社團 --- ## 謝謝大家byebye