演算法是什麼

演算法是由能夠一步步解決問題的步驟所組成，就像是料理新手學習做一道菜時，通常會跟著食譜一步一步做出來，這時候「食譜」可以說是做出料理的演算法。

假設我今天想學做麻婆豆腐，所以去 Google 麻婆豆腐該怎麼做，結果發現有超多食譜在教人怎麼做出麻婆豆腐，接下來就要開始考量以下問題，選出一份適合我的麻婆豆腐食譜：

根據這份食譜，我大概需要花多久時間才能做出來？
家裡放得下食譜中需要採買的食材嗎？
食譜中需要的食材或廚具會不會很貴？
不想出門買菜的話，我能根據這份食譜用家中現有的食材做嗎？
如果我照著這份食譜做，有信心做出成功的麻婆豆腐嗎？

好的演算法 vs 不夠好的演算法

如果把一個電腦程式看作演算法，就像食譜一樣，需要考慮類似的問題，而衡量這些問題的評估方式也不同：

花的時間 → 時間複雜度
佔用的空間 → 空間複雜度
正確率 → 實際跑過超多次，看看是否都能成功；或者以理論判斷
相容性 → 在 Windows 跟 MacOS 分別跑過，看是否能運作
開發成本 → 是不是需要額外學習新的理論或技術

複雜度 Complexity

複雜度的全稱是「漸進複雜度」，主要是從時間與空間的角度來評估演算法的好壞。

時間複雜度（Time Complexity）：執行時間的長短
空間複雜度（Space Complexity）：佔用的儲存空間大小

複雜度會受到量級影響，不同時間複雜度／空間複雜度的演算法，在處理大規模資料時，可以看出在時間與空間上的優劣差異。

精確衡量複雜度的方式：大歐跟小歐

說到要比較不同演算法的複雜度，要比較的是當資料量變多時，演算法成長的速度。

假設演算法動一次步驟，花費的時間都是一樣的，這個步驟次數就是 n。因為要模擬處理大規模資料的情境，所以會假想當 n 趨近無窮大來比較複雜度。

極限概念 1
當 n 趨近無窮大，哪個總和會比較大？

$3n^2 + n + 20$ 與 $100n$
$n^{100}$ 與 $2^n$
$n^2$ 與 $10_nlog n$
$100^n$ 與 $n!$
$30*2^n$ 與 $3^n$
$100n$ 與 $200n$

極限的概念 2
上面的比較方式，只單純比較總和結果，但如果只比較總和結果其實不準，就像 A 第一次跟第二次的考試成績分別是 80 跟 100，B 則是 40 跟 50，但 $\frac{80}{40} = \frac{100}{50}$，兩人的進步幅度（成長速度）是相同的，而複雜度要比較的也是成長的速度，為了知道成長的速度差距，就會像前面計算兩人成績的方式一樣，將比較的兩個數相除

在 n 趨近無限大時，$\frac{f(n)}{g(n)}$ 的結果趨近於 0，表示 f(n) 的成長速度比 g(n) 小
在 n 趨近於無限大時，$\frac{f(n)}{g(n)}$ 的結果也趨近於無限大，表示 f(n) 的成長速度比 g(n) 大
否則當兩者是一樣量級，也就是成長速度差不多快

現在問題來了，由於都在假設 n 趨近無限大的情況下比較複雜度量級，每次都要假裝將 n 帶入後心算結果，不論怎麼想都覺得麻煩，所以有了特殊符號，能以簡潔的方式表示複雜度，方便人快速做判斷。這些特殊符號有很多種類，這裡只說明大歐（Big-O）、小歐（Little-o）跟（Big-theta）三種。

大歐（Big-O）

通常記為 $O(f(n))$
$f(n)$ 指的是複雜度量級的上界（最大值），實際執行的結果可能會比用（Big-O）紀錄的數值小。

以下是將演算法改用為大歐符號表示的例子：

演算法算式	複雜度符號
$3n^2 + n + 20$	$O(n^2)$
$100n$	$O(n)$
$n^{100}$	$O(n^{100})$
$2^n$	$O(2^n)$
$n^2$	$O(n^2)$
$10nlog n$	$O(nlogn)$
$100^n$	$O(100^n)$
$n!$	$O(n!)$
$100n$	$O(n)$
$3^n$	$O(3^n)$
$30*2^n$	$O(2^n)$
$200n$	$O(n)$

下圖則表示當資料量變多時，每種大歐需要執行的步驟，例如：$O(1)$ 表示輸入的數值大小與需要執行的步驟無關，執行步驟不受輸入數值影響。

小歐（Little-o）

記為 $o(f(n))$
$f(n)$ 指的是複雜度量級的嚴格上界（絕對的最大值），代表實際執行的數值一定會比轉成 $o(f(n))$ 紀錄的數值小

例如 $3n^3 + 5n^2 + 10n + 3$，以大歐（Big-O）紀錄是 $O(n^3)$，但在小歐（Little-o）要記錄成 $o(n^4)$。兩者的複雜度量級不同。

(Big-theta)

記為 $θ(f(n))$
$f(n)$ 指的是複雜度量級的嚴格上下界，實際執行的數值與（Big-theta）紀錄的數值完全相同。代表不管用哪種複雜度符號紀錄，結果都屬於相同複雜度量級，不會像 $3n^3 + 5n^2 + 10n + 3$，以不同複雜度符號紀錄時，會有不同結果。

這篇文章大致說明了演算法的概念、評估演算法好壞的方式、不同的時間複雜度量級、表示時間複雜度的方式。由於剛接觸演算法，還沒真實體驗到演算法在實務開發的重要性，較難以實際案例比較不同複雜度的演算法。但跟著程式導師計畫的課程進度往下走，下篇內容預計是排序用的演算法，順便了解一個演算法的最理想情況與最壞情況。