{%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)$

for (int i = 0 ; i < n ; i++) {
    // do something
}

----

### O($n^2$)

for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < n ; j++) {
        // do something
    }
}

----

注意這裡是用 big-O ，所以以下情況也是 $O(n^2)$

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>

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 不需要用也可以。

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

----