---
# System prepended metadata

title: ADA 1.2 Asymptotic Analysis
tags: [ADA 1.2, Asymptotic Analysis]

---

###### 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)$
