{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> # 演算法 --- <h2 style='color:#C4C400'> 介紹 </h2> 演算法不是程式語言。演算法是用來解決特定問題的方法與過程。 一個定義良好的計算方式，會包含單一，或一組完整的輸入，並且產生出一個值，或一組值作為輸出，如果所有輸出的值都是正確答案，則說明解決了問題。 ---- <h3 style='color:#C4C400'> 例子 </h3> 假設今天要解決一個問題是：「如何把芋頭和牛奶，做成芋頭牛奶」 1. 將芋頭切塊蒸至熟透。 2. 將芋泥蒸熟後先放入白糖攪拌均勻。 3. 再放入奶油攪拌均勻，最後加入牛奶時再將芋頭壓成泥狀即完成。 可以說這3個步驟就是把芋頭和牛奶做成芋頭牛奶的一種演算法 ---- <h3 style='color:#C4C400'> 為什麼要學演算法? </h3> - 學習演算法可以了解在不同規模下的表現和效率，性能通常決定了什麼是可行的，什麼是不可能的。 - 透過學習算法，了解不同的思維，特別在離散的框架上，很多時候和一般思維下會有一些不同的看法，以及觀點。 - 加強理論的實現，如果只懂理論，從來沒實作過，很容易會導致遇到問題的時候，根本不知道怎麼下手，或者使用了所謂的 "笨" 方法。 ---- 在電腦科學中有一條公式：  ---- <h3 style='color:#C4C400'> 無所不能 ？ </h3> 所謂的電腦，可不只單純是主機、筆電，具上述計算能力的最小單位就是一個晶片，而晶片早就被廣泛應用在我們生活之中，像是遙控器，手機，電視，火警，保全。 所以只要具備計算能力硬體在的地方我們就需要演算法，也因此有演算法可以改變世界之說。 ---- <h3 style='color:#C4C400'> 電腦並不聰明，反而很笨，對，電腦超級笨，超級無敵笨!!! </h3> 根據三個特性，發明了一種方式叫做 **Programming** 把現實世界要解決的問題變成數學，丟給電腦來幫我們做運算，所以聰明的並不是電腦，而是背後的人用聰明的方式，讓其他人誤以為電腦很強大，很聰明。 --- <h2 style='color:#C4C400'> 演算法策略 (跳過) </h2> https://hackmd.io/@HIPP0/HkYSwDwds --- <h2 style='color:#C4C400'> 演算法優劣 </h2> 常常聽到有人說，這個效率不好! 另外一個效率比較好，那到底怎麼來比較一個演算法的效率呢？ ---- <h3 style='color:#C4C400'> 目標 </h3> - 描述函數在極限中的行為方式。 - 比較函數的 “大小” 的方法。 - 如何表示算法的運行時間。 - 判斷一個程式(做法)會不會 TLE - 透過測資反推所需的演算法效能 ---- <h3 style='color:#C4C400'> 簡單方程比較 </h3> 這邊簡單說一些常見的方程，在極限中的行為 非常重要的函數關係！！！！ ### 指數函數 > 多項式函數 > 對數函數 > 常數函數 ----  ---- <h3 style='color:#C4C400'> 符號 </h3> 然而描述一個函數有以下幾種方式 (但通常會直接用 big O 居多) - O-notation (big-o or o) - Ω-notation (big-omega) - Θ-notation - o-notation (little-o) - ω-notation (little-omega) ---- <h3 style='color:#C4C400'> 簡單一點的描述你可以看成 </h3> - O ~ <= - Ω ~ >= - Θ ~ = - o ~ < - ω ~ > 所以當我們描述兩個方程 f, g 在趨近極限的狀況 f = O(g) 你就可以大致看成成 f <= g ，以此類推 接下來來進行比較嚴謹的定義 ---- <h3 style='color:#C4C400'> O-notation (big-o or o) ☆☆☆☆☆ </h3> O-notation（大O符號）描述了函數漸近行為的上限 (upper bound)：它表示一個函數的增長速度不會超過某個特定的速率。這個速率是基於最高次項的。 數學上的定義，若 f = O(g)，則存在一個常數 c > 0 使得當 N 夠大的時候，對於所有 n >= N，有 f(n) <= c(g(n)) ---- <h3 style='color:#C4C400'> 舉例來說： </h3> $5x^2 + 3logx + x + 3$ = O($x^2$) $3e^x + 99x^{99}$ = O($e^x$) $3xlogx + 5x$ = O($3xlogx$) ---- <h3 style='color:#C4C400'> 推論題目效率需求 </h3> 程式 (C++) 大概一秒跑 $10^7 ~ 10^8$ 所以如果遇到 n = $10^5$，思考常見的函數 - $O(2^n)$ 很明顯不行 - $O(n^2)$ 不行因為 $n^2$ = $10^10$ - $O(nlogn)$ 可以 $nlogn$ = $10^6$ - $O(n)$ 可以 - $O(1)$ 肯定可以 ---- <h3 style='color:#C4C400'> 例子 </h3> - 判斷質數 - 美麗島 - 菜就多練 - PPAP --- <h2 style='color:#C4C400'> 常見演算法分析 </h2> ---- ### $O(n)$ ```cpp= for (int i = 0 ; i < n ; i++) { // do something } ``` ---- ### O($n^2$) ```cpp= for (int i = 0 ; i < n ; i++) { for (int j = 0 ; j < n ; j++) { // do something } } ``` ---- 注意這裡是用 big-O ，所以以下情況也是 $O(n^2)$ ```cpp= for (int i = 0 ; i < n ; i++) { for (int j = i ; j < n ; j++) { // do something } } ``` 因為 $\frac{1}{2}(n)(n+1)$ = $O(n^2)$ ---- <h3 style='color:#C4C400'> 二分 (logn) </h3> ```cpp= int arr[5] = {1,2,3,4,5}; int left = 0, right = 5; int target; cin >> target; while (left < right) { int mid = (left + right)/2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } cout << "index = " << (left + right)/2; ``` ---- <h3 style='color:#C4C400'> 為什麼二分會是 (logn) </h3> 假設區間大小是 n ，二分的時候每次都會讓區間大小縮小一半 第 1 次找: $\frac{n}{2}$ 第 2 次找: $\frac{n}{4}$ $....$ 第 k 次找: $\frac{n}{2^k}$ 當 $\frac{n}{2^k}$ 等於 1 的時候停止搜尋 所以得到 $\frac{n}{2^k} = 1$ $k = log_2n = O(logn)$ ---- <h3 style='color:#C4C400'> 遞迴 </h3> 簡單的可以直接看出來的 (讚!) 複雜遞迴: 可以使用 master theorem 來判斷 太複雜的?? ---- <h3 style='color:#C4C400'> 輸入輸出問題 </h3> 雖然複雜度可以估計，但實際上輸入輸出的時間也是耗費很大，所以為了避免掉這個問題，會使用，但基本上 CPE 不需要用也可以。 ```cpp= ios::snyc_with_stdio(false),cin.tie(0); ``` (畢竟如果卡了輸入輸出，就看不出演算法實際效率了，例如圖論題目，需要大量 node 以及 edge 的時候，通常輸入挺龐大的) ---- <h3 style='color:#C4C400'> 常見內建函數 </h3> - memset O(N) - sort O(NlogN) - __gcd / gcd (c++17) O(logN) - lower_bound / upper_bound / equal_bound O(logN) - vector insert O(N) !! ---- <h3 style='color:#C4C400'> 練習 </h3> - E001 ----