-
1 # 資料結構和演算法
-
2 # 勝己半子
概念
演算法（Algorithm）是基於特定的計算模型， 旨在解決某一資訊處理問題而設計的一個指令序列。不正式地說，演算法是任何定義明確的計算過程，該過程取某個值或值的集合作為輸入，併產生某個值或值的集合作為輸出，演算法就是這樣的把輸入轉換成輸出的計算步驟的一個序列。[1]
必備特徵
演算法必須具有以下特徵：
輸入：待計算問題的任一例項，都需要以某種方式交給對應的演算法，對所求解問題特定例項的這種描述統稱為輸入；
輸出：經計算和處理之後得到的資訊，即針對輸入問題例項的答案，稱作輸出；
確定性：演算法應可描述為由若干語義明確的基本操作組成的指令序列；
可行性：每一基本操作在對應的計算模型中均可兌現；
有窮性：任意演算法都應在執行有限次基本操作之後終止並給出輸出。
實際例子
演算法不是計算機領域中才有的概念，不僅僅侷限於程式語言，它可以用任何方式來描述，比如對於問題：過直線l上給定的點P，作該直線的垂線。古埃及人解決該問題的一個演算法為：
輸入：直線l及其上一點P
輸出：經過P且垂直於l的直線
1. 取12段等長繩索，依次首尾聯結成環，聯結處稱作“結”，按順時針方向編號為0到11
2. 奴隸A看管0號結，將其固定於點P處
3. 奴隸B牽動4號結，將繩索沿直線l方向儘可能地拉直
4. 奴隸C牽動9號結，將繩索儘可能地拉直
5. 經過0號和9號結，繪製一條直線
計算機中的演算法則是描述計算機上的計算過程，比如插入排序演算法的虛擬碼描述：
輸入：n個數的一個序列<a[1], a[2], ..., a[n]>
輸出：輸入序列的一個排列<b[1], b[2], ..., b[n]>，滿足b[1] <= b[2] <= ... <= b[n]
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
上述演算法可以用不同的程式語言來描述，比如用Python描述：
def insertSort(A):
for j in range(2, len(A)):
key = A[j]
i = j - 1
while i > 0 and A[i] > key:
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
比如用C++描述：
template<typename T>
void insertSort(std::vector<T>& A)
{
for (int j = 2; j < A.size(); ++j)
{
auto key = A[j];
int i = j - 1;
while (i > 0 && A[i] > key)
{
A[i + 1] = A[i];
--i;
A[i + 1] = key;
}
}
}
優劣分析
由於計算機不是無限快，記憶體不是免費的，計算時間和空間是一種有限資源，高效的演算法可以更好地利用這些資源，因此演算法可以像計算機硬體一樣視為一種技術。度量演算法成本的方式稱為複雜度分析，複雜度可分為時間複雜度和空間複雜度。由於執行任一演算法的空間消耗都不會多於執行期間進行的基本操作次數，即時間複雜度本身就是空間複雜度的上界，因此複雜度分析主要關注時間複雜度，而時間複雜度分析主要關注最壞情況下的執行時間，即最長執行時間。複雜度分析一般用漸進記號大O表示，它用一個函式來描述某個函式的數量級上界。最低複雜度是O(1)，代表常數時間複雜度，因為不能指望沒有任何代價來執行演算法。依次遞增的常見覆雜度層級還有O(log n)、 O(√n)、O(n)、O(nlog n)、O(n^2)、O(n^3）、O(2^n)等。
常見種類
計算機中儲存和組織資料的方式稱為資料結構，因此計算機中的演算法通常也與資料結構緊密相連，最常見的一類演算法就是資料結構的插入、刪除、查詢、遍歷、排序等，一般此類演算法會封裝為程式語言的標準之一，如C++ STL中的演算法。除了資料結構相關演算法外，還有圖演算法、數論演算法、矩陣運算、計算幾何、壓縮演算法、加密演算法、資料探勘演算法、並行演算法等。演算法設計與分析的基本方法有蠻力法、分治法、動態規劃、貪心演算法等。並非所有問題都存在有效演算法，對於NP完全問題是否存在有效演算法是未知的。[2]
回覆列表
1，陣列
2，佇列（先進先出）
3，棧（先進後出）
4，連結串列（包括單向的，雙向的，環形的，還有跳錶）
5，HashMap（陣列加連結串列的結合）
6，樹（常見的有二叉樹，紅黑色，字典樹，B-樹，樹的形式非常多）
7，堆（屬於二叉樹的一種，並且是一棵完全二叉樹）
7，圖（有向圖，無向圖）