###### tags: `ADA 1.2` `Asymptotic Analysis`
# ADA 1.2 Asymptotic Analysis
## Motivation
- 冠軍問題用比較次數當作難度比較的對象
- 但是每個問題都有不一樣的丈量單位，所以希望每個問題都有一個通用的評估單位
- 不考慮單位和係數，只專注在 function 成長的速率
---
## Goal: Finding Hardness
- 對於問題 P，我們希望弄清楚
- 問題 P 的難度(複雜度) = $\Theta(f(n))$
- n 代表問題 P 的實例的大小，例如剛剛的冠軍問題輸入 n 個數字找到冠軍
- n 就是藉由不同實例給予不同數值的，$f(n)$ 就是 n 的 function
- $\Theta(f(n))$ 意思就是他剛剛好等於這個 function 的成長速率
- 所以如果我們要藉由比較的方式找出冠軍的話
- 冠軍問題的難度會是 $\Theta(n)$
- 為什麼是 n 不是 n - 1 呢？ 因為兩個 function 的成長速度是一樣的，所以 -1 可以省略
- 而不管是 n 還是 2n 因為成長速率也是一樣的，所以前面的係數也可以省略
- 另一個 sorting 的問題的難度是 $\Theta(n\log n)$ 之後會講到
- 用 Upper bound 和 Lower bound 找出難度
- 當 Upper bound 和 Lower bound 一樣時就可以找出這個問題的難度
- Upper bound 通常會希望找到比較低的
- 用 $O(f(n))$ 和 $o(f(n))$ 表示
- Lower bound 通常會希望找到比較高的
- 用 $\Omega(g(n))$ 和 $\omega(g(n))$ 表示
如果一個問題的 Upper bound 是 $O(h(n))$ Lower bound 是 $\Omega(h(n))$\
問題的複雜度就會是 $\Theta(h(n))$\
$\Theta$就是兩邊都成立的意思
- 找到問題的難度就需要先分析/評估演算法的
- 時間複雜度
- 空間複雜度
- 大部分我們都會專注在**最差情況下**的複雜度，因為我們的演算法需要解決這個問題的所有實例，連最難的都要解決
- 不過後面也會有需要用**平均情況下**來分析，例如：最差的情況在這個問題中，出現的情況非常非常低
|Types |Description |
|----------------|-------------------------|
|Worst Case |任何一個實例最多需要花多少時間|
|Average Case |花的時間的**期望值** |
用 $O$ 表示演算法的 upper bounds 在最壞情況下的時間複雜度
用 $\Omega$ 表示演算法的 lower bounds 在最壞情況下的時間複雜度
---
## 漸進分析符號
**Textbook ch. 3.1**
- $f(n)$ = 輸入n大小的演算法的時間或空間
- 漸進分析: 當 $n \rightarrow \infty$ 時 $f(n)$ 的成長速率
- O or Big-Oh: **upper** bounding function
- $\Omega(n)$ or Big-Omega: **lower** bounding function
- $\Theta(n)$ or Big-Theta: **tightly** bounding function
## 正式定義 Big-Oh
**Textbook ch. 3.1**
- 給兩個 function $f(n)$ 和 $g(n)$
$$f(n) = O(g(n))$$
如果成立的話，對於所有 $n\ge n_0$ 以下式子都要成立
$$0\le f(n) \le c\cdot g(n) $$
$n_0$ 和 c 是常數
:::info
$g(n)$的某個常數倍$c\cdot g(n)$ 可以在 n 夠大時壓得住 $f(n)$
:::
- 直覺的想像是 $f(n)$ 的成長速率不會比 $g(n)$ 來得快
- 註釋
1. $f(n) = O(g(n))$ 的意思就是 $f(n)$ 的成長速率就某方面來說小於等於 $g(n)$
2. 這裡的 "=" 不是 "等於" 的意思，比較像屬於 "$\in$"\
$\{f(n)\} \subseteq O\big(g(n)\big)$
3. 寫的時候順序不能寫反了如：$O(g(n)) = f(n)$
- 注意
- $f(n)$ 和 $g(n)$ 的 n 可以是負數
- 因為不管是 $O, \Omega$ 我們都是考慮當 n 足夠大的時候，所以當 n 足夠大的時候我們大都是考慮非負的情況
## 漸進分析符號
- 優點：
- 可以省略 low-order terms: $n^2+n$ 後面的 n 就可以省略
- 可以省略單位
- 可以省略係數
- 可以簡化分析
- Example $f(n) = 5n^3+7n^2-8$
- Upper bound: $f(n) = O(n^3), f(n) = O(n^4), f(n) = O(n^3log_2 n)$
- Lower bound: $f(n)=\Omega(n^3), f(n)=\Omega(n^2), f(n)=\Omega(nlog_2 n)$
- Tight bound: $f(n)=\Theta(n^3)$
- Q: $f(n) = O(n^3)$ and $f(n) = O(n^4)$，可以說$O(n^3) = O(n^4)$嗎？
A: 不行，因為這邊的等於不是等於的概念，是屬於
---
## 練習
$100n^2=O(n^3-n^2)?$
- 草稿(這部分只要在腦子或計算紙上寫就好了)
$$100n^2\le100(n^3-n^2)$$
$$\leftarrow 200n^2\le100n^3$$
$$\leftarrow 2\le n$$
- $n_0=2,c=100$ (證明這件事情只要寫這以下的就好了)
$$100n^2\le100(n^3-n^2)$$
當 $n \ge 2$, $100n^2=O(n^3-n^2)$ 成立
## 練習
$n^2=O(n)$?
- 反證法
- 假設一個矛盾的條件，存在一個正的常數 $c, n_0$ 讓
$$n^2 \le cn$$
任何 n 符合 $n \ge n_0$
- 假設 $n=1+\lceil max(n_0,c)\rceil$
所以 $n > n_0, n > c$，可以推導出 $n^2 > cn$
- 矛盾，所以我們知道 $n^2 \ne O(n)$
TODO: 遇到問題\
雖然知道怎麼推導出來的，但是我還是不知道一開始的 $n=1+\lceil max(n_0,c)\rceil$ 這個式子是從哪裡來的？
:::info
$n_0 \in\mathbb N, \space n \ge n_0$
**Prove**:
$let\space c \ge 0$
$\space \space \space \space \space n \ge n_0$
=> $n \ge n_0 + c$
=> $n \ge n_0 + c + 1$
=> $f(c) \ge n_0 + c + 1$
=> $n = 1 + max(n_0,\space c)$
:::
---
## 規則
**Textbook ch. 3.1**\
教授說不用背，因為非常的直覺，看過就好
- Rule1: $f(n) = O(f(n))$
- Rule2: 如果 c 是正的常數，$c \cdot O(f(n)) = O(f(n))$
- Rule3: 如果 $f(n) = O(g(n))$，然後 $O(f(n)) = O(g(n))$
- Rule4: $O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))$
- Rule5: $O(f(n) \cdot g(n)) = f(n) \cdot O(g(n))$
## 其他的符號
- $f(n)=O(g(n))\rightarrow f(n) \le g(n)$ 的成長率
- $f(n)=\Omega(g(n))\rightarrow f(n) \ge g(n)$ 的成長率
- $f(n)=\Theta(g(n))\rightarrow f(n) = g(n)$ 的成長率
- $f(n)=o(g(n))\rightarrow f(n) < g(n)$ 的成長率 (沒有等於 比較少用到)
- $f(n)=\omega(g(n))\rightarrow f(n) > g(n)$ 的成長率 (沒有等於 比較少用到)
---
## 演算法分析
- 擂台法
```
1. int i, j; O(1) time
2. j = 1; O(1) time
3. for(i = 2; i <= n; i++) O(n) iterations
4. if(A[i] > A[j]) O(1) time
5. j = i; O(1) time
6. return j; O(1) time
```
全部加起來 -> upper bound 在最壞情況下的時間複雜度
$O(1)+O(1)+O(n)\cdot(O(1)+O(1))+O(1)$
$3\cdot O(1)+O(n)\cdot(2O(1))$
$=O(1)+O(n)\cdot O(1)$ (Rule 2)
$=O(1)+O(n)$ (Rule 4)
$=O(n)+O(n)$ (1 = O(n) & Rule 3)
$=2\cdot O(n)$ (Rule 2)
$=O(n)$
TODO: 遇到問題\
1 = O(n) 我還沒想明白…
:::info
$\space \space \space \space \space O(1) + O(n)$
=> $f(n) +O(g(n))$ -> (Rule3)
=> $O(f(n)) + O(g(n))$
=> $O(g(n)) + O(g(n))$
=> $O(n)$
:::warning
老實說我覺得這一步很多餘 by woody
:::
---
## 排序問題
練習另一題
- Input:
An array A of n distinct integers.
- Output:
Reorder A such that A[1]<A[2]<…<A[n].
## 演算法分析
- 泡沫排序法
```
1. int i, done; O(1) time
2. do { f(n) iterations
3. done = 1; O(1) time
4. for (i = 1; i < n; i++) { O(n) iterations
5. if (A[i] > A[i + 1]) { O(1) time
6. exchange A[i] and A[i + 1]; O(1) time
7. done = 0; O(1) time
8. }
9. }
10. } while (done == 0)
```
- Upper bound
$O(1)+f(n)\cdot(O(1)+O(n)\cdot O(1))$
$=O(1)+f(n)\cdot O(n)$
$=f(n)\cdot O(n)$
$=O(n^2)$
其中$f(n) = O(n)$要用歸納法證明
---
## 演算法分析
- 擂台法
```
1. int i, j; Big-Omega(1) time
2. j = 1; Big-Omega(1) time
3. for(i = 2; i <= n; i++) Big-Omega(n) iterations
4. if(A[i] > A[j]) Big-Omega(1) time
5. j = i; Big-Omega(1) time
6. return j; Big-Omega(1) time
```
- lower bound
$3\cdot\Omega(1)+\Omega(n)\cdot(2\cdot\Omega(1))$
$=\Omega(1)+\Omega(n)\cdot\Omega(1)$
$=\Omega(1)+\Omega(n)$
$=\Omega(n)$
Lower bound 可以直接這樣做嗎？？？
- 先來看看百般無聊擂台法
```
1. int i; Big-Omega(1) time
2. int m = A[1]; Big-Omega(1) time
3. for (i = 2; i <= n; i++) { Big-Omega(n) iterations
4. if (A[i] > m) Big-Omega(1) time
5. m = A[i]; Big-Omega(1) time
6. if (i == n) Big-Omega(1) time
7. do i++ n times Big-Omega(n) time
8. }
9. return m; Big-Omega(1) time
```
如果 Lower bound 真的可直接這樣加起來的話
$3\cdot\Omega(1)+\Omega(n)\cdot(3\cdot\Omega(1)+\Omega(n))$
$=\Omega(1)+\Omega(n)\cdot\Omega(n)$
$=\Omega(1)+\Omega(n^2)$
$=\Omega(n^2)$
就會變成這樣，但實際上不能這樣算，因為只有 i==n 的時候才會多做那n次無意義的事情，如果把它乘進去就會造成高估，但我們現在算的是 lower bound 不能隨便高估
所以比較保險的估算方式是從問題實例裡估算
---
## 演算法分析
- 泡沫排序法
```
1. int i, done; Big-Omega(1) time
2. do { f(n) iterations
3. done = 1; Big-Omega(1) time
4. for (i = 1; i < n; i++) { Big-Omega(n) time
5. if (A[i] > A[i + 1]) { Big-Omega(1) time
6. exchange A[i] and A[i + 1]; Big-Omega(1) time
7. done = 0; Big-Omega(1) time
8. }
9. }
10. } while (done == 0)
```
當 A 是從大排到小, $f(n)=\Omega(n)$
最壞情況下泡沫排序法的時間複雜度是
$f(n)\cdot\Omega(n)=\Omega(n^2)$
Sign in with Wallet
Connect another wallet