---
# System prepended metadata

title: ADA 1.3 Algorithm Complexity
tags: [Algorithm Complexity, ADA 1.3]

---

###### tags: `ADA 1.3` `Algorithm Complexity`
# ADA 1.3 Algorithm Complexity

# Time Complexity of an Algorithm

- 演算法 A 的時間複雜度是$\Theta(f(n))$
    代表的意思是
1. 演算法 A 可以在$O(f(n))$時間跑完
2. 演算法 A 在最壞的情況下至少需要$\Omega(f(n))$的時間
    - 有一個實例$I(n)$會讓演算法 A 需要跑到$\Omega(f(n))$的時間

---

## Tightness of the Complexity

- 如果我們說這個複雜度分析是 **tight** 最好的、最緊的，表示 $O(f(n))$ 這個 Upper bound 是**最低的**
- 也就是說他在最壞情況下是 $\Omega(f(n))$ (**最高的** Lower bound)
- = 這個演算法在最壞情況下的複雜度是$\Theta(f(n))$

- 把泡沫排序演算法帶進來看，如果我們說他的 Upper bound $O(n^2)$ 是 tight 的話
- 代表這個演算法的 Lower bound 就是 $\Omega(n^2)$
- 也就是說這個演算法的複雜度就是$\Theta(n^2)$

---

## Algorithm Analysis

- 百般無聊擂台法

```c
1.  int i;                      Big-Oh(1) time
2.  int m = A[1];               Big-Oh(1) time
3.  for (i = 2; i <= n; i++) {  Big-Oh(n) iterations
4.     if (A[i] > m)            Big-Oh(1) time
5.         m = A[i];            Big-Oh(1) time
6.     if (i == n)              Big-Oh(1) time
7.         do i++ n times       Big-Oh(n) time
8.  }
9.  return m;                   Big-Oh(1) time
```

==非常不 tight 的分析 來分析 Upper bound==

$3\cdot O(1)+O(n)\cdot(3\cdot O(1)+O(n))$

$=O(1)+O(n)\cdot O(n)$

$=O(1)+O(n^2)$

$=O(n^2)$

==用 tight 的方式分析==
第三行的迴圈用了 $O(n)$ ，只有在最後得時候才又多做 $O(n)$ 次，所以我們不能把他算到迴圈裡面，所以第三到第八行花的時間就是：

$O(n)\cdot O(1)+1\cdot O(n)=O(n)$

一樣的分析用在 Lower bound 就是 $\Omega(n)$

:::info
💡 在最壞情況下百般無聊擂台法的複雜度就是 $\Theta(n)$.
:::

---

## Algorithm Comparison

- Q: 如果以下成立，我們可以說演算法 1 比演算法 2好嗎？
    - 演算法 1: $O(n)$ 的時間
    - 演算法 2: $O(n^2)$ 的時間

- A: 不行！因為上面的 Upper bound 並沒有說他是 tight 的，就沒辦法確定他們的 Lower bound，所以不能只憑 Upper bound 就來比較

---

## Comparing A and B

- 演算法 A 不比演算法 B 差，在某些最壞的情況下，如果存在一個 $f(n)$
    - 演算法 A 用了 $O(f(n))$ 的時間(有可能 Lower bound 更好)
    - 演算法 B 在最壞情況下至少要用 $\Theta(f(n))$ 的時間
    - 代表 $A \le B$
- 如果說演算法 A 嚴格的比 B 好的話表示
    - 演算法 A 用 $O(f(n))$ 的時間(O 表示 $\le$)
    - 演算法 B 在最壞情況下要用 $\omega(f(n))$ 的時間($\omega$表示>)
    或者
    - 演算法 A 用 $o(f(n))$ 的時間(o 表示 <)
    - 演算法 B 在最壞情況下要用 $\Omega(f(n))$ 的時間($\Omega$ 表示 $\ge$)

---

# Problem Complexity

問題的難度

---

## Time Complexity of a Problem

- 如果我們說問題 P 的難度是 $\Theta(f(n))$
1. 問題 P 難度的 Upper bound 是 $O(f(n))$
    - 代表存在一個花$O(f(n))$時間解決問題 P 的演算法
2. 問題 P 難度的 Lower bound 是 $\Omega(f(n))$
    - 代表**任何**可以解決問題 P 的演算法都至少需要 $\Omega(f(n))$ 的時間

- 冠軍問題的難度是 $\Theta(n)$ 是因為
1. 冠軍問題難度的 Upper bound 是 $O(n)$
    - 擂台法花 $O(n)$ 的時間解決
2. 冠軍問題難度的 Lower bound 是 $\Omega(n)$
    - 代表**任何**可以解決冠軍問題的演算法都至少需要 $\Omega(n)$ 的時間 (至少都要比較 n - 1 次)

---

## Optimal Algorithm

- 如果說演算法 A 是**最好的演算法**就代表
    - 演算法 A 花了 $O(f(n))$ 的時間，而且
    - 問題 P 的難度至少也有 $\Omega(f(n))$ 這麼難
    - 代表沒有多花多餘的力氣剛好就能解決問題 P

- 例如 (冠軍問題)
    - 擂台法 → 最好的演算法
        - 他花了 $O(n)$ 的時間解決
        - 任何可以解決冠軍問題的演算法都至少需要 $\Omega(n)$ 的時間
    - 百般無聊擂台法 → 最好的演算法
        - 他花了 $O(n)$ 的時間解決
        - 任何可以解決冠軍問題的演算法都至少需要 $\Omega(n)$ 的時間

---

## Comparing P and Q

- 問題 P 不會比問題 Q 更難，如果下面的情況成立的話
    - P 的難度是 $O(f(n))$
    - Q 的難度是 $\Omega(f(n))$

- 問題 P 一定比 Q 簡單的話
    - P 的難度是 $O(f(n))$
    - Q 的難度是 $\omega(f(n))$
    或是
    - P 的難度是 $o(f(n))$
    - Q 的難度是 $\Omega(f(n))$

---

# 結論

- 演算法分成設計和分析兩個部分
- Algorithm Design and Analysis Process
    :::info
    設計
    - 確定問題
    - 設計演算法
    :::
    :::warning
    分析
    - 證明正確性
    - 分析需要多少時間/空間
    :::
- 大部分的問題都可以用暴力法解決只是沒有效率
- 分析的技巧
    - 反證法
    - 歸納法
    - 漸進分析
    - 問題實例
- 演算法複雜度
    - 在最壞情況下演算法的成長速率
- 問題難度
    - 在最壞情況下可以解決這個問題的最好的演算法要花多少時間

最後要做 Ch.3 Growth of function 的習題，pdf 輸入頁數 73
3.1-1
Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of ‚$\Theta$notation, prove that $max(f(n),g(n)) = \Theta(f(n) + g(n))$


3.1-2
Show that for any real constants a and b, where b>0,
$(n+a)^b = \Theta(n^b)$

3.1-3
Explain why the statement, “The running time of algorithm A is at least $O(n^2)$,” is meaningless.
試著回答 Upper bound 沒有說明是 tight 的話沒有意義，因為有可能 Lower bound 可以更快

3.1-4
Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?

3.1-5
Prove Theorem 3.1.
頁數 69 $\Omega$-notation 的下面

3.1-6
Prove that the running time of an algorithm is ‚$\Theta(f(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.

3.1-7
Prove that $o(g(n)) \bigcap \omega(g(n))$ is the empty set.（$\bigcap$交集的意思）

3.1-8
We can extend our notation to the case of two parameters n and m that can go to
infinity independently at different rates. For a given function $g(n, m)$, we denote
by $O(g(n, m))$ the set of functions
$$
O(g(n, m)) = \{f(n, m):there\space exist\space positive\space constants\space c, n_0, and\space m_0\\
such\space that\space 0\le f(n, m)\le cg(n, m)\\
for\space all\space n\ge n_0, m\ge m_0
\}
$$
Give corresponding definitions for $\Omega(g(n, m))$ and $\Theta(g(n, m))$ 



