資料結構與演算法筆記 - 什麼是演算法？又是如何衡量其效能的？
今天介紹演算法的空間 / 時間複雜度等的概念，關於資料結構跟演算法的筆記我一直都很想寫文章紀錄一下，因為這些東西有些久沒碰，概念其實會滿模糊的，而且因為雖然我常常寫程式，有些資料結構及演算法也不會常常在專案中用到，所以就會導致生疏。
常寫程式經驗告訴我，其實有事沒事多想想一些演算法的東西是可以多活絡自己頭腦的，很多人都說書上的資料結構跟演算法學了也沒用，根本不會在實際上用到，其實… 是會用到，會這樣想是因為主流的程式語言早就對這些資料結構及演算法的東西進行封裝並提供 Lib 給你使用，而我們需要學的是解決問題的精神及每個資料結構善用的場景，才能去優化我們的程式。
演算法介紹
定義
完成特定功能之有限個指令 / 敘述，所成之集合，且滿足以下五個性質
- Input (輸入)：外界提供 **≥ 0 ** 個輸入 Data 數量
- Output (輸出)：至少需有 **≥ 1 ** 個輸出結果
- Definiteness (明確性)：因為 algorithm 的撰寫格式沒有一定的規範格式，所以每個指令 / 敘述必須是 clear and unambiguous
- Finiteness (有限性)：在執行有限次 step 後，必須能夠終止
- Effectiveness (有效性)：每個指令 / 敘述必須足夠基本可讓人用紙筆來 trace algorithm
Note：Program 與 Algorithm 的差異在於說，Program 不一定滿足有限性，Program 可以 Infinite Execution，例如：人為設計 Error、實際應用所需。
演算法效能 (Performance) 評估
評估演算法的 Performance 有兩個 criteria：
- Space Complexity
- Time Complexity
Space Complexity (空間複雜度)
令 S§ 是 Program P 之空間需求，則 S§ = C + S (I)，C 是正常數。
- C 代表的是固定空間 (fixed space)
- Instruction (code) space
- 變數空間
- 常數空間
- Fixed Size 結構型變數：array、struct、object
- S (I) 代表的是變動空間 (variable space)
- 參數是結構型且是 call-by-value 傳遞
- stack 空間 for recursion
Time Complexity (時間複雜度)
令 T§ 代表 Alg/Program P 之時間需求，則 T§ = Development time + Execution time。
通用的計算方法：
運用 Analysis 技巧，統計 Algo/Program 中指令執行次數總和來做為預估未來執行時間之基礎。
漸進式符號 (Asymptotic Notation)
代表是時間複雜度的 Growing Rate 之等級，分別有以下等級：
- Big-oh：O
- Omega：$\Omega$
- Theta：$\Theta$
- little-oh: o
- little-omega：$\omega$
Big-oh 介紹
f(n) = O(g(n)) if exists two positive constants c and n~0~，such that|f(n)| <= c |g(n)|, for all n >= n~0~
Big-oh 被視為 f (n) 之理論的 upper-bound (上限值)
例子一
$f(n) = 3n^2 + 2 ≤ 4n^2\ for\ n≥2 $
$g(n)=n^2$
可以找出 $n_0 = 2$, c = 4
所以我們可以說：$f (n) = O (n^2)$
訣竅：其實 c 可以隨機找，通常就是看最高次項的常數去多加一之類的就可以了，接著就可以透過等式去解出 n~0~ 的值
例子二
$f(n) = 10n^3+100n=O(n^3)$
其實要判斷它的 Big-oh 只要看最高次方即可
例子三
$f(n)=a_mn^m+a_{m-1}n^{m-1}+…+a_1n^1+a_0=O(n^m)$
一樣，直接看最高次方，因此是 $O (n^m)$
Omega 介紹
$f(n)=\Omega(g(n))$ if exists two positive constants $c\ and\ n_0$, such that $|f(n)|≥c|g(n)|, for\ all\ n≥n_0$
Omega 被視為 f (n) 之理論的 lower-bound (下限值)
例子一
$f(n)=3n^2+2≥3n^2\ for\ n≥1$
解出來就變成是 2≥0，恆正，所以 n~0~ 任取即可，通常會取最小值，也就是取 1
所以可以知道 $f (n)=\Omega (n^2)$
訣竅：其實 c 可以隨機找，通常就是直接拿最高次項的常數就可以了，接著就可以透過等式去解出 n~0~ 的值
例子二
$f(n)=5n^2+8n-16$
如果要算 Omega 直接取最高次方即可：
$f(n)=\Omega(n^2)$
Theta 介紹
$f(n)=\Theta(g(n))$ if exists three positive constants $c_1$、$c_2$、$n_0$，such that $c_1|g(n)|≤|f(n)|≤c_2|g(n)|\ for\ all\ n≥n_0$
Note：
-
$\Theta$ is more precise than O and $\Omega$
-
$f (n)=O (g (n))\ 且 \ f (n)=\Omega (g (n))\ <=>\ f (n)=\Theta (g (n))$
例子一
$2n^2≤f(n)=3n^2+2≤4n^2\ for\ n≥2$
找法很簡單，直接看最高項的常數各自加減就可以找出這樣的等式
所以可以知道 $f (n)=\Theta (n^2)\ n_0=2,\ c_1=2,\ c_2=4$
例子二
$f(n)=5n^2+8n-16$
取 $c_1$=5 => $5n^2+8n-16≥5n^2$ => n≥2
取 $c_2$=6 => $5n^2+8n-16≤6n^2$ => $n^2-8n+16≥0$ => n≥1
根據上面的 n 的範圍，因此應該要取 n≥2，才能符合整個等式：
$5n^2≤5n^2+8n-16≤6n^2\ for\ n≥2$
因此可以知道 $f (n)=\Theta (n^2)$
little-oh 介紹
跟 big-oh 定義差在：f (n) = O (g (n)) if exists two positive constants c and n~0~，such that |f (n)| < c |g (n)|, for all n >= $n_0$
不包含 **=**
例子一
$f(n)=3n^2=o(n^3)$
little-omega 介紹
跟 omega 定義差在：$f (n)=\Omega (g (n))$ if exists two positive constants $c\ and\ n_0$, such that $|f (n)|≥c|g (n)|, for\ all\ n≥n_0$
不包含 **=**
例子一
$f(n)=3n^2=\omega(n)$
時間複雜度等級比較
常數等級
例子：
$O(1)=\ 2^{100}=\ 10^{10}=\ 5000=\ 2^{1000}$
對於時間複雜度來說，只要是常數等級的話其實都視為 O (1)，因為常數是固定的數字，他並不會隨著輸入資料的不同而增加時間，所以不要誤會了！
對數等級
例子：
$$
log^{*}n<loglogn<\sqrt[2]{logn}<logn<log^dn=(logn)^d,\ d>1
$$
通常演算法中 log 都是以 2 為底，也不會特別寫出來。
多項式等級
通常只要演算法的時間複雜度是在多項式時間內，就會稱該演算法為 polynomial algorithm。
多項式等級的例子：
$$
n^{0.01}<\sqrt[2]{n}<n<nlogn<n^2<n^d,\ d>2
$$
指數等級
通常只要演算法的時間複雜度沒辦法限制在多項式時間內，就會稱該演算法為 exponential algorithm。
指數等級的例子：
$$
(1.01)^n<1.5^n<2^n<d^n,\ d>2
$$
階層等級
例子：
$$
(n-1)!<n!<(n+1)!
$$
總結
所以可以知道在演算法的時間複雜度中，常數等級 < 對數等級 < 多項式等級 < 指數等級 < 階層等級。
最好、平均、最壞時間複雜度情況
通常演算法的時間複雜度還會分最好、平均、最壞的情況來做分析，而看這個演算法好不好都會先看這個演算法的最壞情況來做評估，而最好的情況通常不會去參考，平均的情況也常常會拿來參考。
最好情況 (Best Case)
也就是演算法在最理想情況下執行的時間複雜度最低
平均情況 (Average Case)
也就是演算法在所有情況下執行的時間複雜度透過加權的方式進行計算，有點類似期望值的概念。
最壞情況 (Worst Case)
也就是演算法在最壞情況下執行的時間複雜度最高
Note：請不要把最好、平均、最壞情況誤以為就是 Big-oh、Omega、Theta 的概念，兩者是不一樣的東西。只是說通常演算法在寫這些 case 的時間複雜度時都會用 Big-oh 來寫，這是代表這個 case 情況下的 upper-bound (上限值) 的概念！
總結
如果之後有空會多多發一些文章是關於常見的演算法及資料結構的程式碼實現及概念講解，其實就是我當年考研究所的內容而已 XD
最後最後！請聽我一言！
如果你還沒有註冊 Like Coin，你可以在文章最下方看到 Like 的按鈕，點下去後即可申請帳號，透過申請帳號後可以幫我的文章按下 Like，而 Like 最多可以點五次，而你不用付出任何一塊錢，就能給我寫這篇文章的最大的回饋！