程式語言概念-演算法

程式語言概念
演算法

演算法基本上，分成排序、搜尋、最短路徑單源、最短路徑多源、最小生成樹、最大流量最小割、拓樸排序、線性規劃、hash function、近似、隨機、分制法、動態編程、貪婪等議題的討論，在進行程式優化時，會對函式庫所使用到的演算法，重新撰寫，以節省編譯跟載入時間。
以下就依序對上述議題進行討論，另外比較的時候，需要用同樣的資料結構進行比較。

---

交換(Swap)

最基本的概念，用於把兩筆資料的記憶體位置互換，所有演算法都會用到。

排序

排序主要目的是對資料進行值得比較，並依照大小順序排序，由小開始，亦可由大開始。

以下是排序演算法種類，氣泡、選擇、插入、快速、合併、堆疊、桶

氣泡：最簡單的排序演算法，把數值大的往後移動或是把數值小的往前移動，另有同時進行兩種動作的shaker sort。

選擇：找尋最小值或最大值，並將移動到最前位置之後，依序知道所有元素執行完成。

插入：把資料分成已完成排序的區域以及未完成的區域，並把未完成區域的資料不停放入已完成的區域。

快速*：選定一直當作基準值，與基準值比較交換資料位置，再將基準值兩側的值進行前述排序，直到排序結束。

合併*：分制法應用，把資料拆成小資料在合併。

堆疊*(二元堆疊)：以樹的結構進行排序，把樹中最大的值移動在上放位置，之後數字再依序排序，此演算法是利用樹的搜尋速度的優勢。

桶*：把資料分到個別的桶中進行排序，然後再合併。

常用的排序法有，快速、合併、堆疊、桶，快速為大多語言預設的演算法，合併需要額外的記憶體，堆疊目前應用來進行排序執行順序，桶在資料龐大時可以拆散資料進行排序。

各種排序時間複雜度比較

搜尋

搜尋主要目的是為了對已經建立的資料結構，對其內容進行搜尋，搜尋特定的資料，所以針對不同的資料結構會有不同的演算法，常見的有Linear Search、binary tree Search、深度優先搜尋、廣度優先搜尋、A*

Linear Search：一一比對進行搜尋

binary tree Search：把資料轉成binary tree(有排序過的)後，再進行搜尋，缺點需要花費時間轉乘binary tree。

深度優先搜尋：對樹或圖進行搜尋，在搜尋時會以深度作為優先，會往下走直到無法往下走為止

廣度優先搜尋：對樹或圖進行搜尋，在搜尋時會以寬度作為優先，會往旁枝走直到沒有旁枝為止

A*:主要用於圖的資料結構，用來搜尋兩點之間的路徑。

最短路徑單源

主要用來解決兩點最短路徑問題，常見的有Dijkstra's algorithm(不可以有負權重)、Bellman–Ford algorithm(可以有負環)、Floyd-Warshall algorithm(可以有負權重，但不可以有負環)。

最短路徑多源

同最短路徑單源，並重複對各源進行運算。

最小生成樹

找尋圖中，連接所有點的最小權重生成，並把結果存成樹，也就是把圖轉成樹，此樹的權重是此圖的最小權重，常見的有Prime、Krustal。

最大流量最小割

最大流量就等於割最小流量，也就是把圖分成兩邊，而把圖型分成兩邊的那條線，就是所謂的割，而最大流量必定不能超過此割，此割的流量必須最小，有最大流量最小割定理對此進行證明，常見演算法有ford-fulkerson、edmonds-karp，用於網絡需要最大流量，如管路、網路或財務決策。

拓樸排序

DAG圖才能進行拓樸排序，可以把流程中的活動進行排序，決定順序。

線性規劃

線性規劃是在優化問題中的重要地位，在作業研究中遇到的問題，都可以處理。

hash function

MD5、SHA1用於加密、壓縮、解壓縮的演算法。

近似

最部分進行最佳化，常用的有線性規劃、貪婪演算法。

隨機

在演算法中加入隨機函數。

分治法

分治法是將問題拆成小問題、運算、再合併，但是這些小問題彼此之間無關連性。

動態規劃

動態規劃是將問題用數學模型描述，並拆成小問題、運算、再合併，但是這些小問題彼此之間有關連性。

貪婪

貪婪是將問題拆成小問題、運算、再合併，但是運算是對小問題最佳化。

---

練習-高中生解題系統-https://cat.nknush.kh.edu.tw/