演算法 complexity 學習筆記（一）

無論是演算法設計還是演算法優化，我們都避免不了衡量演算法的最重要指標complexity 複雜度。

先看一下定義：

• 首先一個演算法需要一個input 輸入值，一些處理步驟procedure， 最後給出一個結果output。
• 演算法是實際問題的分步驟解決方式。(Algorithms are procedural solutions to problems).
• 演算法解決方案（algorithmic solutions）可以分為四個基本種類:

1. run in "reasonable time"- class of tractable problems(e.g. sorting,searching). 易處理問題，可以在合理時間內完成的，如排序問題，搜索問題等。
2. do not have "reasonable time"(the Travelling Salesman problem). 第二類沒有固定的合理處理時間，如旅行推銷員問題（圖論問題Graphical Model,過幾天我應該也會複習到Graphical Models）
3. 第三類絕對沒有合理處理時間的演算法。（漢諾塔）
4. 第四類不能寫出演算法的問題。（non-commutable problems ）如halting problem（停機問題），下圖是wiki上面關於停機問題的介紹。

• 兩周常用的分析演算法的方式：

1. Empirical 經驗法：repeatedly run algorithm with different inputs- get some ideas on different sizes of input. 嘗試不同的輸入值看不同效果。
2. Theoretical 理論法： 目的是比較 time demand需要時間 跟 input size大小的關係

Time Complexity Function Problem Size n

10 10^2 10^3 10^4

log2(n) 3.3 6.6 10 13.3

n 10 100 1000 10000

nlog2(n) 33 700 10000 1.3x10^5

n^2 100 10000 10^6 10^8

n^3 1000 10^6 10^9 10^12

2^n 1024 1.3x10^30 >10^100 >10^100

n! 3x10^6 >10^100 >10^100 >10^100

1. 計算演算法複雜度，第一步要計算input size， 輸入值大小。（根據實際文本分析）
2. 第二步要統計花費時間（time taken）

• 機器獨立的時間統計machine independent measure of time： 統計初級操作數目elementary operations（unit cost，unit time）. （如排序演算法中，我們把每次比較作為初級操作elementary operation， 初級操作可以有 Boolean operation（and， or， not， etc）Assignment(賦值)，數學計算加減乘除。
• 通常兩數字相乘被認為是 elementary operation， 但是當相乘兩數字過大或者小數點後位數過多是，乘法的成本就不再微小了，需要將乘法分成更小的操作，用更好的演算法將數字分開相乘（Strassens Algorithm）。
• 分析時間複雜度 time-complexity analysis 需要分析三種情況：最好情況，平均情況，最壞情況 Worst Case， Average Case，Best Case（best worst case）。
• O 表達式：f(n) is O(g(n)) 表示： 隨著n變大，f(n) 的增長速度不大於 g(n)的速度。

1. O(k*f(n)) = O(f(n)) 任意常數k
2. O(f(n)+g(n)) = O(max(f(n),g(n)))
3. O(f(n)) U O(g(n)) = O(f(n)+g(n)) = O(max(f(n),g(n)))