資料結構和演算法簡介
本篇目前為 Wiki 頁面的簡易整理，暫時還無法全部用我的方式表達；
由於是來自 Wiki 的資料因此也會遵循相同的分享規範。
--
Bruce:
資料結構是代表儲存資料的特定方法；不同的儲存排列方法會使得新增刪除修正查詢資料的速度有所改變，對於特定的狀況可以設計使用不同的資料結構來加快達成目的的執行速度。目前常用程式語言中的陣列與矩陣等最終端應該都會是使用某種資料結構來實作以實現高效率，如 C++ 中 STL 的 container 可能是使用紅黑樹之類的。
接著我將列舉數種資料結構作為範例。
Wiki:
一般而言，資料結構的選擇首先會從抽象資料類型的選擇開始。一個設計良好的資料結構，應該在盡可能使用較少的時間與空間資源的前提下，為各種臨界狀態下的執行提供支援。資料結構可通過編程語言所提供的資料類型、參照及其他操作加以實作。
在許多類型的程式設計中，選擇適當的資料結構是一個主要的考慮因素。許多大型系統的構造經驗表明，封裝的困難程度與最終成果的品質與表現，都取決於是否選擇了最優的資料結構。在許多時候，確定了資料結構後便能很容易地得到演算法。而有些時候，思路則會顛倒過來：例如當某個關鍵作業需要特定資料結構下的演算法時，會反過來確定其所使用的資料結構。然而，不管是哪種情況，資料結構的選擇都是至關重要的。
系統構造的關鍵因素是資料結構而非演算法的這一深入理解，導致了多種形式化的設計方法與程式語言的出現。絕大多數的語言都帶有某種程度上的模組化思想，通過將資料結構的具體實作封裝隱藏於受限介面之後的方法，來讓不同的應用程式能夠安全地重用這些資料結構。C++、Java、Python等物件導向的程式語言可使用類來完成這一功能。
鏈結串列 (Linked List)
Bruce:
鏈結串列是在一筆資料節點中附加指標來導向下一筆資料節點位置的一種資料結構，這代表著存取後續的資料時需要順藤摸瓜得從開始找到目標。新增資料時可以從任一資料節點將它所記錄的下筆位置修改為欲新增的資料節點位置，而新增的資料節點本身再指向原本的下一筆資料即可。
Wiki 中所提到的 O(n) 所指的是上限時間 big-O，n 代表資料量的大小，意即 O(n) 與資料量時間成正比；O(1) 則代表所需時間與資料量無關，為常數時間；O(logn) 代表所需上限時間的關係只需要對數量 n 取 log 即可。
Wiki:
鏈結串列（Linked
list）是一種常見的基礎資料結構，是一種線性表，但是並不會按線性的順序儲存資料，而是在每一個節點裡存到下一個節點的指標(Pointer)。由於不必須按順序儲存，鏈結串列在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是尋找一個節點或者存取特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。
一個單向連結串列包含兩個值: 當前節點的值和一個指向下一個節點的連結
來源：
佇列 (Queue)
Bruce:
佇列這個資料結構的概念是：只准將新進資料排在目前資料列的尾端，並且刪除時只能從頭開始刪除。
Wiki:
稱佇列，又稱為隊列（queue），是先進先出（FIFO,
First-In-First-Out）的線性表。在具體應用中通常用鍊表或者數組來實現。佇列只允許在後端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作。
Representation of a FIFO (first in, first out) queue
來源：
堆疊 (Stack)
Bruce:
堆疊的概念如同一種 "只准對最上方物品拿放的籃子"：新增時只准加入在最上方，刪除時也只准從最上方物件開始刪除。在特定情況時會是一種非常有效率的資料結構。
Wiki:
堆疊資料結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。
堆疊資料結構使用兩種基本操作：推入（push）和彈出（pop）：
● 推入：將數據放入堆疊的頂端（陣列形式或串列形式），堆疊頂端top指標加一。
● 彈出：將頂端數據資料輸出（回傳），堆疊頂端資料減一。
堆疊的簡單示意圖
來源：
二元樹 (Binary Tree)
Bruce:
二元樹是一種最基礎且重要的樹結構，當它滿足不同的特定條件時，又可以被定義為某種特定的樹結構。
Wiki:
在電腦科學中，二元樹（英語：Binary
tree）是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二元樹常被用於實現二元搜尋樹和二叉堆。
一個簡單的二元樹
來源：
AVL Tree
Bruce:
AVL 樹是一種較為複雜卻又並不是非常複雜的樹，具有不錯的操作時間，實作上也不會太困難。一般對 AVL 樹操作所稱的旋轉其實是指將樹依據被插入節點或刪除後的狀況重新調整頂端節點 (稱為：根，Root) 關係的行為。
Wiki:
以下圖表以四列表示四種情況，每行表示在該種情況下要進行的操作。在左左和右右的情況下，只需要進行一次旋轉操作；在左右和右左的情況下，需要進行兩次旋轉操作。
插入
向AVL樹插入，可以透過如同它是未平衡的二元搜尋樹一樣，把給定的值插入樹中，接著自底往上向根節點折回，於在插入期間成為不平衡的所有節點上進行旋轉來完成。因為折回到根節點的路途上最多有1.44乘log
n個節點，而每次AVL旋轉都耗費固定的時間，所以插入處理在整體上的耗費為O(log n) 時間。
刪除
從AVL樹中刪除，可以透過把要刪除的節點向下旋轉成一個葉子節點，接著直接移除這個葉子節點來完成。因為在旋轉成葉子節點期間最多有log n個節點被旋轉，而每次AVL旋轉耗費固定的時間，所以刪除處理在整體上耗費O(log n) 時間。
搜尋
來源：
紅黑樹
Wiki:
性質1. 節點是紅色或黑色。
性質2. 根是黑色。
性質3. 所有葉子都是黑色（葉子是NIL節點）。
性質4. 每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)
下面是一個具體的紅黑樹的圖例：
這些約束確保了紅黑樹的關鍵特性: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的
高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二元搜尋樹。
要知道為什麼這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。
在很多樹資料結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些性質並使算法複
雜。為此，本文中我們使用 "nil 葉子" 或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際
上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。
Bruce:
見下方特徵，為演算法之核心定義。
Wiki:
在數學和計算機科學/算學之中，演算法/算則法（Algorithm）爲一個計算的具體步驟，常用於計算、資料處理和自動推理。精確而言，演算法是一個表示爲有限長[1]清單的有效方法。演算法應包含清晰定義的指令[2]用於計算函式[3]。
演算法中的指令描述的是一個計算，當其執行時能從一個初始狀態和初始輸入（可能爲空）開始，[4]經過一系列有限[5]而清晰定義的狀態最終產生輸出[6]並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
特徵
1. 輸入：一個演算法必須有零個或以上輸入量。
2. 輸出：一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。
3. 明確性：演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。
5. 有效性：又稱可行性。能夠實作，演算法中描述的操作都是可以通過已經實作的基本運算執行有限次來實作。
基本要素
演算法的核心是建立問題抽象的模型和明確求解目標，之後可以根據具體的問題選擇不同的模式和方法完成演算法的設計。
來源：
氣泡排序法 (Bubble Sort)
Wiki:
氣泡排序演算法的運作如下：
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
3. 針對所有的元素重複以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
使用氣泡排序為一列數字進行排序的過程
分類 排序演算法
Python程式碼
def bubble(List):
for j in range(len(List)-1,0,-1):
for i in range(0,j):
if List[i]>List[i+1]:List[i],List[i+1]=List[i+1],List[i]
return List
for j in range(len(List)-1,0,-1):
for i in range(0,j):
if List[i]>List[i+1]:List[i],List[i+1]=List[i+1],List[i]
return List
範例：
testlist = [27, 33, 28, 4, 2, 26, 13, 35,
8, 14]
print('final:', bubble(testlist))
print('final:', bubble(testlist))
輸出： final: ([2, 4, 8, 13, 14, 26, 27, 28, 33, 35])
來源：
插入排序法 (Insertion Sort)
Wiki:
一般來說，插入排序都採用in-place在數組上實現。具體算法描述如下：
1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置後
6. 重複步驟2~5
使用插入排序為一列數字進行排序的過程
分類 排序算法
Python
def insertion_sort(n):
if len(n) == 1:
return n
b = insertion_sort(n[1:])
m = len(b)
for i in range(m):
if n[0] <= b[i]:
return b[:i]+[n[0]]+b[i:]
return b + [n[0]]
if len(n) == 1:
return n
b = insertion_sort(n[1:])
m = len(b)
for i in range(m):
if n[0] <= b[i]:
return b[:i]+[n[0]]+b[i:]
return b + [n[0]]
Python的另一個版本
def insertion_sort(lst):
if len(lst) == 1:
return
for i in xrange(1, len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and temp > lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
if len(lst) == 1:
return
for i in xrange(1, len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and temp > lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
來源：
快速排序法 (Quick Sort)
Bruce:
快速排序是 20 世紀最偉大的演算法之一，「分而治之、各個擊破」這單純易懂的核心概念與其優秀的執行速度在深刻瞭解後將令人感受到演算法之美。
Wiki:
快速排序採用「分而治之、各個擊破」的觀念，此為原地（In-place）分割版本。
步驟為：
1. 從數列中挑出一個元素，稱為"基準"（pivot），
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。
使用快速排序法對一列數字進行排序的過程
分類 排序演算法
Python
def qsort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
return qsort([x for x in arr[1:] if x < pivot]) + \
[pivot] + \
qsort([x for x in arr[1:] if x >= pivot])
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
return qsort([x for x in arr[1:] if x < pivot]) + \
[pivot] + \
qsort([x for x in arr[1:] if x >= pivot])
來源：
貪婪演算法 (Greedy Algorithm)
Bruce:
貪婪演算法是一種非常易懂與實作的演算法，但唯有在問題是能夠由「之前每步都做最佳選擇仍能導致最終獲得最佳結果」的情況下才適合使用。
Wiki:
貪心法，又稱貪心演算法，是一種在每一步選擇中都採取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。[1]比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。
貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。
貪心法可以解決一些最優化問題，如：求圖中的最小生成樹、求哈夫曼編碼……對於其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助算法或者直接解決一些要求結果不特別精確的問題。
細節
1. 建立數學模型來描述問題。
2. 把求解的問題分成若干個子問題。
3. 對每一子問題求解，得到子問題的局部最優解。
4. 把子問題的解局部最優解合成原來解問題的一個解。
實現該算法的過程：
從問題的某一初始解出發；while 能朝給定總目標前進一步 do ,求出可行解的一個解元素；
最後，由所有解元素組合成問題的一個可行解。
Greedy algorithms determine minimum number
of coins to give while making change. These are the steps a human
would take to emulate a greedy algorithm to represent 36 cents using only coins
with values {1, 5, 10, 20}. The coin of the highest value, less than the
remaining change owed, is the local optimum. (Note that in general the
change-making problem requires dynamic programming or integer programming to find an optimal
solution; however, most currency systems, including the Euro and US Dollar, are
special cases where the greedy strategy does find an optimal solution.)
動態規劃法 (Dynamic Programming)
Bruce:
核心概念在於透過末端各種選擇的組成，向上前進時使用較好的組成 (即在末端時可能並非最佳選擇)，從而能夠至頂端時做出一條最佳選擇路徑。
Wiki:
動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合併子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
來源：
範例：矩陣鏈相乘
Bruce: 由於矩陣的大小會影響到所需要的乘法數量，因此決定出好的矩陣相乘先後順序將能有效的減少所需要的計算量。
Main article: Matrix chain multiplication
Matrix chain multiplication is a well known
example that demonstrates utility of dynamic programming. For example,
engineering applications often have to multiply a chain of matrices. It is not
surprising to find matrices of large dimensions, for example 100×100.
Therefore, our task is to multiply matrices
A1, A2, .... An. As we know from basic linear algebra, matrix multiplication is
not commutative, but is associative; and we can multiply only two matrices at a
time. So, we can multiply this chain of matrices in many different ways, for
example:
((A1 × A2) × A3)
× ... An
A1×(((A2×A3)×
... ) × An)
(A1 × A2) × (A3
× ... An)
and so on. There are numerous ways to
multiply this chain of matrices. They will all produce the same final result,
however they will take more or less time to compute, based on which particular
matrices are multiplied. If matrix A has dimensions m×n and matrix B has
dimensions n×q, then matrix C=A×B will have dimensions m×q, and will require
m*n*q scalar multiplications (using a simplistic matrix multiplication
algorithm for purposes of illustration).
Dijkstra 最短路徑演算法
Wiki:
戴克斯特拉演算法（英語：Dijkstra's
algorithm）是由荷蘭電腦科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜尋解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，該演算法可以用來找到兩個城市之間的最短路徑。
留言
張貼留言