什麼是演算法？

# 什麼是演算法？演算法(Algorithm)是透過一系列的步驟、規則或計算，來解決特定問題或完成某項任務所需的資訊。常見的演算法用途，如：排序、搜尋、最佳路徑、加/解密、機器學習、影像處理等。 $$ 輸入(Input) + 演算法(Algorithm) = 輸出(Output) $$ 如果以日常生活舉例，餐廳廚師將多種食材依照食譜的洗、切、調味/醃製、煮/蒸/煎/炸等一系列的操作，烹調出一道美味的佳餚。而食譜就可視為美味佳餚的演算法 $$ 食材 + 食譜 = 美味佳餚 $$ 透過以上，我們可以簡單歸納出演算法的特徵包括 1. 明確性：需明確清晰的定義步驟，無歧義 2. 有限性：需在有限的步驟內完成任務或解決指定問題 3. 輸入及輸出：需有零個或一個以上的輸入，以及需有至少一個輸出 # 演算法的評估當我們依據特定問題，定義出解決的演算法時，我們要如何評估該演算法的好壞？演算法的執行或計算過程，不外乎皆需要時間與記憶體(空間)，來支持演算法的執行過程。所以，我們可以依據執行該演算法，所需耗費的時間長短，以及所佔用的記憶體(空間)大小，來評估演算法的好壞。 # 複雜度（Complexity）所需耗費的時間長短，我們可以使用「時間複雜度(Time Complexity)」來表示。而所佔用的記憶體(空間)大小，我們可以使用「空間複雜度(Space Complexity)」來表示。其中需注意的是，時間複雜度所評估的時間，是指執行步驟的次數，而非指執行所需的時間。 因為執行所需的時間，不僅與演算法的定義相關，還與執行背景有所關聯。 以程式的角度來看，相同的輸入資料及演算法，若是用不同的程式語言撰寫，或是用不同規格的桌電/筆電/VM執行，演算法所需的時間也就不會一致。若以日常生活舉例，相同的麵團，使用家用的烤箱以及使用餐廳的專業烤箱，兩種不同功率的烤箱，執行烘烤所需的時間也不會一致。因此，在時間複雜度中，所紀錄的時間是指執行步驟的次數，而非指實際的執行時間。 一般而言，演算法會隨著輸入項(n)的不同，而有對應的時間或空間改變，比如 : ```= int n = 10, sum = 0; for(int i=0;i<n;i++){ sum++; } ``` 以時間角度來說，迴圈的次數會隨著n而改變，輸入項(n)與時間成正比關係。若以f(n)表示，這段程式執行所需的時間可記為 $$ f(n) = n $$ 用圖表畫出則會呈現線性的樣子 ![f(n) = n](https://hackmd.io/_uploads/BJQAahT-yg.png) 假設再將程式調整為雙層迴圈 ```= int n = 10, sum = 0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ sum++; } } ``` 迴圈則會執行 `n^2` 次，可記為 $$ f(n) = n^2 $$ ![f(n) = n^2](https://hackmd.io/_uploads/S1ixb6p-Jg.png) 綜上所述，我們可以簡單從輸入項(n)的改變，歸納出執行次數 f(n) 的變化。 ## 多項式當然，一般能夠解決問題的演算法，也不會單純的只有一個迴圈，通常會由多個步驟的程式碼所組成。假設我們將前述兩段程式碼，視為同一個演算法的「步驟一」及「步驟二」，其演算法的總執行次數可記為 $$ f(n) = n^2 + n $$ 當其複雜度為多項式，且所輸入的輸入項(n)越大時，最高次方項的值，佔該函數總值的比例也就越大。以 $f(n) = n^2 + n$ 的多項式來看，假設 n = 10,000 ``` f(n) = (10,000 * 10,000) + 10,000 = 100,000,000 (99.99%) + 10,000 (0.01%) = 100,010,000 (100%) ``` 我們可以觀察出「最高次方項的值，是影響函數總值的最大因素」，至於多項式的其他項目則可忽略不計。 # 漸進符號（Asymptotic Notation）實務上一般會使用大Ｏ符號來表達其複雜度的漸進式。然而，漸進式的表達方法不僅有大Ｏ符號，還有其他如：大Ω符號、大θ符號等。 * 大Ｏ符號，Big-O(O) 表示演算法的上限/上界(Upper Bound)，即「最壞的執行狀況」 * 大Ω符號，Big-Omega(Ω) 表示演算法的下限/下界(Lower Bound)，即「最好的執行狀況」 * 大θ符號，Big-Theta(θ) 表示演算法的上、下限/界，其描述「含蓋所有的執行狀況」而演算法中，通常大家比較關注的點是最少需要耗費多久的時間，以及最少需要多少的記憶體，才能夠成功執行完成所有的情境，所以我們可以簡單用演算法的上限/上界(Upper Bound)來看，即「最壞的執行狀況」。也因此，演算法的時、空間複雜度的表達，通常使用大Ｏ符號表示居多。每種漸進符號皆有對應的數學式，詳細可再參考其他文獻。 # 如何判斷複雜度？那麼我們平常開發程式時，可以如何判斷所撰寫的程式碼，是屬於哪一種「時間複雜度」以及哪一種「空間複雜度」？針對這兩大部分，因為需要說明的地方較多，另拆成兩篇文章來進行說明。其中內容也涵蓋一些常見開發情境的時、空間複雜度判斷。 [時間複雜度](https://hackmd.io/@Lion-Le/rkrvv1qMke) [空間複雜度](https://hackmd.io/@Lion-Le/ByTtSQ771g) # 重點歸納簡單為這一系列的演算法文章做個重點整理 * 演算法的定義演算法是指透過一系列的步驟、規則或計算，來解決特定問題或完成某項任務所需的資訊 * 演算法的特性 1. 明確性：需明確清晰的定義步驟，無歧義 2. 有限性：需在有限的步驟內完成任務或解決指定問題 3. 輸入及輸出：需有零個或一個以上的輸入，以及需有至少一個輸出 * 演算法的評估演算法的好壞可透過「時間複雜度」以及「空間複雜度」兩點來綜合評估，兩者分別代表「執行所需耗費的時間」以及「執行所需耗費的空間(記憶體)」 * 複雜度的表示法可使用「漸進符號」表示其複雜度的漸進方式 * 漸進符號的種類可依據所需評估的面向，如：最佳情境、最壞情境、平均情境等使用其對應的「漸進符號」，以下為幾種常見的漸進符號 1. 大Ｏ符號，Big-O(O) 表示演算法的上限/上界(Upper Bound)，即「最壞的執行狀況」。是評估複雜度中最常用的「漸進符號」 2. 大Ω符號，Big-Omega(Ω) 表示演算法的下限/下界(Lower Bound)，即「最好的執行狀況」 3. 大θ符號，Big-Theta(θ) 表示演算法的上、下限/界，其描述「含蓋所有的執行狀況」 * 常見的演算法二元搜尋法(Binary Search)、遞迴(Recursion)、深度優先搜尋(Depth-First Search，DFS)、廣度優先搜尋(Breadth-First Search，BFS)、動態規劃(Dynamic Programming，DP）以及各種排序法，如：氣泡排序、選擇排序、合併排序等 # 總結對於百萬、千萬資料量級以上的系統，或是資源較為有限的嵌入式設備、IOT主機板等使用情境，會需要特別注意「時間複雜度」與「空間複雜度」對於其他中、小型系統而言，時間複雜度不要達到指數級`O(2^n)`以上，空間複雜度不要達到平方級`O(n²)`以上，大多時候皆為可容忍程度資料量級越大的系統，在執行不同複雜度的程式時，感受上也會相對的顯著至此，演算法系列的文章大概告個段落，這系列的文章，僅簡單提及與說明演算法的各個觀念。若對其觀念有興趣或想再更深入研究者，可再參考其他演算法的文獻、書籍或資源等。 >[!Tip] 文章內容皆為個人整理的觀點，以及整理後的個人想法，如內容有錯誤或疑慮的部分，歡迎提出討論，收到後會盡快修正！