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