算法設計與分析基礎

• 第一章 緒論
• • 1.1 什麼是算法
  • 1.2 算法問題求解基礎
  • • 1.2.1 了解問題
    • 1.2.2 了解計算裝置的性能
    • 1.2.3 在精确解法和近似解法之間做出選擇
    • 1.2.4 算法的設計技術
    • 1.2.5 确定适當的資料結構
    • 1.2.6 算法的描述
  • 1.4 基本資料結構
  • • 1.4.2 圖
• 第三章 蠻力法
• • 3.1 選擇排序和冒泡排序
  • • 3.1.1 選擇排序
    • 3.1.2 冒泡排序
  • 3.2 順序查找和蠻力字元串比對
  • • 3.2.1 順序查找
    • 3.2.2 蠻力字元串比對
  • 3.4 窮舉查找
  • • 3.4.1 旅行商問題
    • 3.4.2 背包問題
  • 3.5 深度優先查找和廣度優先查找
  • • 3.5.1 深度優先查找
    • 3.5.2 廣度優先查找
• 第四章 減治法
• • 4.1 插入排序
  • 4.4 減常因子算法
  • • 4.4.1 折半查找
• 第五章 分治法
• • 5.1 合并算法
• 第九章 貪婪技術
• • 9.1 Prim算法
  • 9.2 Kruskal算法
  • 9.3 Dijkstra算法
• 其他
• • 斐波那契數列
  • 裝配線排程

第一章 緒論

1.1 什麼是算法

1. 算法是一系列解決問題的明确指令。

2. (1)算法的每一個步驟都必須沒有歧義，不能有半點兒含糊；

   (2)必須認真确定算法所處理的輸入的值域；

   (3)同一算法可以用幾種不同的形式來描述；

   (4)同一問題，可能存在幾種不同的算法；

   (5)針對同一問題的算法可能基于完全不同的解題思路，而且解題速度也會有顯著不同。

1.2 算法問題求解基礎

1.2.1 了解問題

1. 算法的輸入，确定了該算法所解問題的一個執行個體。
2. 嚴格确定算法需要處理的執行個體範圍非常重要。
3. 正确的算法能正确處理所有合法的輸入。

1.2.2 了解計算裝置的性能

1. 順序算法：指令逐條運作，每次執行一步操作。
2. 并行算法：可以在同一時間執行多條操作，即并行計算。

1.2.3 在精确解法和近似解法之間做出選擇

1. 精确算法：精确解題。
2. 近似算法：近似解題。

1.2.4 算法的設計技術

1. 算法設計技術(也稱為“政策”或者“範例”)是用算法解題的一般性方法，用于解決不同計算領域的多種問題。

1.2.5 确定适當的資料結構

1.2.6 算法的描述

1. 僞代碼：僞代碼是自然語言和類程式設計語言組成的混合結構。

1.4 基本資料結構

1.4.2 圖

哈密頓回路：一個對圖的每個頂點都隻穿越一次的回路。

第三章 蠻力法

3.1 選擇排序和冒泡排序

3.1.1 選擇排序

1. 選擇排序開始的時候，找到它的最小元素，然後和第一個元素互動，将最小元素放到它在有序表中的最終位置上。然後從第二個元素開始掃描清單，找到最後n-1個元素中的最小元素，再和第二個元素交換位置，把第二小的元素放在它的最終位置上。一般來說，在對該清單做第i遍掃描的時候(i的值從0到n-2)，該算法在最後n-i個元素中尋找最小元素，然後拿它和Ai交換。

   SelectionSort(A[0..n - 1])

//用選擇排序對給定的數組排序
//輸入：一個可排序的數組A[0..n - 1]
//輸出：升序排列的數組A[0..n - 1]
for i = 0 to n - 2 do
begin
	min = i
	for j = i + 1 to n - 1 do
		if A[j] < A[min] then
			min = j
	swap A[i] and A[min]
end
           

1. 時間複雜度：O(n2)

3.1.2 冒泡排序

1. 比較表中的相鄰元素，如果它們是逆序的話就交換它們的位置。重複多次後，最大的元素就“沉到”清單的最後一個位置。第二遍操作将第二大的元素沉下去。直到n-1遍以後，該清單就排序好了。

   BubbleSort(A[0..n - 1])

//用冒泡排序對給定的數組排序
//輸入：一個可排序的數組A[0..n - 1]
//輸出：升序排列的數組A[0..n - 1]
for i = 0 to n - 2 do
begin
	for j = n - 1 downto i + 1 do
		if(A[j] < A[j - 1]) then
		swap A[j] and A[j - 1]
end
           

1. 時間複雜度：O(n2)

3.2 順序查找和蠻力字元串比對

3.2.1 順序查找

1. 簡單地将給定清單中的連續元素和給定的查找鍵進行比較，直到遇到一個比對的元素(成功查找)，或者在遇到比對元素前就周遊了整個清單(失敗查找)。

   SequentialSearch(A[0..n], K)

//順序查找的算法實作，使用查找鍵來作限位器
//輸入：一個n個元素的數組A和一個查找鍵K
//輸出：第一個值等于K的元素的位置，如果找不到這樣的元素，傳回-1
A[n] = K
i = 0
while A[i] ≠ K do
	i = i +1
if i < n then
	return i
else 
	return -1
           

//輸入：一個n個元素的數列A和一個數字K
//輸出：确定X是否在數列A中
i = 0
while i < n do
begin
	if K == a[i] then
		report "Found!" and stop
	else
		i = i + 1
end
report "Not Found!"
           

1. 時間複雜度

   (1)最好情況：K為第一個數字，O(1)。

   (2)最壞情況：K為最後一個數字或未找到，O(n)。

2. 改進：如果已知給定的數組是有序的，隻要遇到一個大于或等于查找鍵的元素，就停止查找。

3.2.2 蠻力字元串比對

1. 給定一個n個字元組成的串(稱為文本)，一個m(m≤n)個字元的串(稱為模式)，從文本中尋找比對模式的子串。
2. 将模式對準文本的前m個字元，然後從做到右比對每一對相應的字元，直到m對字元全部比對(算法停止)或者遇到一對不比對的字元。在後一種情況下，模式向右移一位，然後從模式的第一個字元開始，繼續把模式和文本中的對應字元進行比較。注意在文本中最後一輪子串比對的起始位置是n-m(假設文本位置的下标是從0到n-1)。

   BruteForceStringMatch(T[0..n - 1], P[0..m - 1])

//實作蠻力字元串比對
//輸入：一個n個字元的數組T[0..n - 1]，代表一段文本
//          一個m個字元的數組P[0..m - 1]，代表一個模式
//輸出：如果查找成功，傳回文本的第一個比對子串中第一個字元的位置，否則傳回-1
for i = 0 to n - m do
begin
	j = 0
	while (j < m) and (P[j] == T[i + j]) do
		j = j + 1
	if j == m then
		return i
end
return -1
           

1. 時間複雜度

   (1)最好情況：模式在文本開頭，O(m)。

   (2)最壞情況：模式在文本末尾或未找到，O(nm)。

3.4 窮舉查找

3.4.1 旅行商問題

1. 要求找出一條n個給定的城市間的最短路徑，使我們在回到出發的城市之前，對每個城市都隻通路一次。
2. 這個問題可以用權重圖來模組化，用圖的定點代表城市，用邊的權重表示城市間的距離。這樣該問題就可以表述為求一個圖的最短哈密頓回路問題。
3. 哈密頓回路：一個對圖的每個頂點都隻穿越一次的回路。
4. 哈密頓回路可以定義為n+1個相鄰頂點V1、V2……Vn、V1的一個序列。其中序列的第一個頂點和最後一個頂點是相同的，而其他n-1個頂點都是互不相同的。假設所有回路都開始和結束于相同的特定頂點。可以通過生成n-1個中間城市的組合來得到所有的旅行線路，計算這些線路的長度，然後求得最短的線路。

3.4.2 背包問題

1. 給定n個重量為w1、w2……wn，價值為v1、v2……vn的物品和一個承重為W的背包，求這些物品中一個最有價值的子集，并且要能夠裝到背包中。
2. 考慮給定的n個物品集合的所有子集，為了找出可行的子集(總重量不超過背包承重能力的子集)，要計算出每個子集的總重量，然後在它們中間找到價值最大的子集。

3.5 深度優先查找和廣度優先查找

3.5.1 深度優先查找

1. 從任意頂點開始通路圖的頂點，然後把該頂點标記為已通路。在每次疊代的時候，該算法緊接着處理與目前頂點鄰接的未通路頂點。如果有若幹個這樣的頂點，可以任意選擇一個頂點。但在實際應用中，選擇哪一個鄰接的未通路候選頂點主要是由表示圖的資料結構決定的。這個過程一直持續，直到遇到一個終點——該頂點的所有鄰接頂點都已被通路過。在該終點上，該算法遠着來路後退一條邊，并試着繼續從那裡通路未通路的頂點。在後退到起始頂點，并且起始頂點也是一個終點時，該算法停止。起始頂點所在的連通分量的所有頂點都被通路過了。如果未通路過的頂點仍然存在，該算法必須從其中任一頂點開始，重複上述過程。

   DFS(G)

//實作給定圖的深度優先查找周遊
//輸入：圖G = <V,E>
//輸出：圖G的頂點，按照被DFS周遊通路到的先後次序，用連續的整數标記
将V中的每個頂點标記為0，表示還“未通路”
count = 0
for each vertex v in V do
	if v is marked with 0
		dfs(v)

dfs(v)
//遞歸通路所有和v相連接配接的未通路頂點，然後按照全局變量count的值
//根據通路它們的先後順序，給它們賦上相應的數字
count = count + 1
mark v with count
for each vertex w in V adjacent to v do
	if w is marked with 0
		dfs(w)
           

3.5.2 廣度優先查找

1. 按照一種同心圓的方式，首先通路所有和初始頂點鄰接的頂點，然後是離它兩條邊的所有未通路的頂點，以此類推，直到所有與初始頂點同在一個連通分量中的頂點都通路過了為止。如果仍然存在未被通路的頂點，該算法必須從圖的其他連通分量中的任意頂點重新開始。
2. 使用隊列來跟蹤廣度優先查找的操作是比較友善的。該隊列先從周遊的初始頂點開始，将該頂點标記為已通路。在每次疊代的時候，該算法找出所有和對頭頂點鄰接的未通路頂點，把它們标記為已通路，再把它們入隊。然後，将對頭頂點從隊列中移去。

   BFS(G)

//實作給定圖的廣度優先查找周遊
//輸入：圖G = <V,E>
//輸出：圖G的頂點，按照被BFS周遊通路到的先後次序，用連續的整數标記
将V中的每個頂點标記為0，表示還“未通路”
count = 0
for each vertex v in V do
	if v is marked with 0
		bfs(v)

bfs(v)
//通路所有和v相連接配接的未通路頂點，然後按照全局變量count的值
//根據通路它們的先後順序，給它們賦上相應的數字
count = count + 1
mark v with count and initialize a queue with v
while the queue is not empty do
	for each vertex w in V adjacent to the front vertex do
		if w is marked with 0
			count = count + 1
			mark w with count
			add w to the queue
	remove the front vertex from the queue
           

第四章 減治法

4.1 插入排序

1. 假設對較小數組A[0…n - 2]排序的問題已經解決，得到了一個大小為n - 1的有序數組。利用這個較小規模的解，将元素A[n - 1]考慮進來，從右到左掃描這個有序數組，直到遇到第一個小于等于A[n - 1]的元素，然後把A[n - 1]插在該元素的後面。

   InsertionSort(A[0..n - 1])

//用插入排序對給定的數組排序
//輸入：n個可排序元素構成的一個數組A[0..n - 1]
//輸出：升序排列的數組A[0..n - 1]
for i = 1 to n - 1 do
begin
	key = A[i]
	pos = i -1
	while pos >= 0 and A[pos] > key do
		A[pos + 1] = A[pos]
		pos = pos - 1
	A[pos + 1] = key
end
           

1. 時間複雜度：O(n2)

4.4 減常因子算法

4.4.1 折半查找

1. 對于有序數組的查找來說，折半查找是一種性能卓越的算法。
2. 比較查找鍵K和數組中間元素A[m]來完成查找工作。如果它們相等，算法結束。如果K＜A[m]，對數組的前半部分執行該操作。如果K＞A[m]，對數組的後半部分執行該操作。

   BinarySearch(A[0..n-1], K)

//實作非遞歸的折半查找
//輸入：一個升序數組A[0..n - 1]和一個查找鍵K
//輸出：一個數組元素的下标，該元素等于K；如果沒有這樣一個元素，傳回-1
first = 0, last = n - 1
while (first <= last) do
begin
	mid = ⌊ (first + last) / 2 ⌋ //⌊⌋ 是floor函數，表示向下取整
	if(K == A[mid]) then 
		return mid
	else if(K < A[mid]) then
		last = mid - 1
	else
		first = mid + 1
end
return -1
           

1. 時間複雜度

   (1)最好情況：K是中間數，O(1)。

   (2)最壞情況：O(log n)。

2. 順序查找的時間複雜度是O(n)，折半查找的時間複雜度是O(log n)，折半查找比順序查找更有效率。

第五章 分治法

1. 分治法可能是最著名的通用算法設計技術。

2. 分治法按照以下方案工作：

   (1)将一個問題劃分為同一類型的若幹子問題，子問題最好規模相同。

   (2)對這些字問題求解(一般使用遞歸方法，但問題規模足夠小時，有時也會利用另一個算法)。

   (3)有必要的話，合并這些子問題的解，以得到原始問題的答案。

3. 遞歸折半查找

   RecurBinarySearch(A[0..n-1], first, last, K)

//實作遞歸的折半查找
begin
	if(first > last) then
		return false
	mid = ⌊ (first + last) / 2 ⌋
	if(K == A[mid]) then
		return true
	if(K < A[mid] then
		return RecurBinarySearch(A, first, mid-1, K)
	else
		return RecurBinarySearch(A, mid+1, last, K)
end
           

5.1 合并算法

1. 對于一個需要排序的數組A[0…n-1]，合并排序把它一分為二：A[0…⌊n/2⌋-1]和A[⌊n/2⌋…n-1]，并對每個子數組遞歸排序，然後把這兩個排好序的子數組合并為一個有序數組。

   MergeSort(A[0..n-1])

   Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])

//遞歸調用MergeSort來對數組A[0..n-1]排序
//輸入：一個可排序的數組A[0..n-1]
//輸出：升序排列的數組A[0..n-1]
if n > 1 then begin
	copy A[0..⌊n/2⌋-1] to B[0..⌊n/2⌋-1]
	copy A[⌊n/2⌋..n-1] to C[0..⌊n/2⌋-1]
	MergeSort(B[0..⌊n/2⌋-1])
	MergeSort(C[0..⌊n/2⌋-1])
	Merge(B, C, A)
           

1. 初始狀态下，兩個指針(數組下标)分别指向兩個待合并數組的第一個元素。然後比較這兩個元素的大小，将較小的元素添加到一個新建立的數組中。被複制數組中的指針後移，指向該較小元素的後繼元素。上述操作一直持續到兩個數組中的一個被處理完為止。然後将未處理完的數組中剩下的元素複制到新數組的尾部。

   Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])

//将兩個有序數組合并為一個有序數組
//輸入：兩個有序數組B[0..p-1]和C[0..q-1]
//輸出：A[0..p+q-1]中已經有序存放了B和C中的元素
i = 0, j = 0, k = 0
while i < p and j < q do
	if B[i] <= C[j] then
		A[k] = B[i]
		i = i + 1
	else 
		A[k] = C[j]
		j = j + 1
	k = k + 1
if i = p then
	copy C[j..q-1] to A[k..p+q-1]
else
	copy B[i..p-1] to A[k..p+q-1]
           

1. 時間複雜度：O(n log n)

第九章 貪婪技術

1. 貪婪法：通過一系列步驟來構造問題的解，每一步對目前構造的部分解做一個擴充，直到獲得問題的完整解為止。所做的每一步選擇都必須滿足以下條件：

   (1)可行的：即它必須滿足問題的限制。

   (2)局部最優：它是目前步驟中所有可行選擇中的最佳的局部選擇。

   (3)不可取消：即選擇一旦做出，在算法的後面步驟中就無法改變了。

2. 通過一系列局部的最優選擇，可能整個問題的(全局的)不是最優解。
3. 生成樹：連通圖的一棵生成樹是包含圖的所有頂點的連通無環子圖(也就是一棵樹)
4. 最小生成樹：權重連通圖的一棵最小生成樹是圖的一棵權重最小的生成樹，其中樹的權重定義為所有邊的權重總和。

9.1 Prim算法

1. 通過一系列不斷擴張的子樹來構造一棵最小生成樹。從圖的頂點集合V中任意選擇的一個單頂點，作為序列中的初始子樹。每一次疊代時，以一種貪婪的方式來擴張目前的生成樹，即把不在樹中的最近頂點添加到樹中(最近頂點是指一個不在樹中的頂點，它以一條權重最小的邊和樹中的頂點相連，而樹的形狀是無所謂的)。當圖的所有頂點都包含在所構造的樹中以後，該算法停止。疊代總次數是n-1，其中n是圖中頂點的個數。
2. 時間複雜度：O(|E| log |V|)

9.2 Kruskal算法

1. 該算法通過對子圖的一系列擴充來構造一棵最小生成樹，這些子圖總是無環的，但在算法的中間階段，并不一定是連通的
2. 該算法在開始的時候，按照權重的非遞減順序對圖中的邊進行排序。然後，從一個空子圖開始，它會掃描這個有序清單，并試圖把清單中的下一條邊加到目前的子圖中。這種添加不應導緻一個回路，如果産生了回路，則把這條邊跳過。
3. 時間複雜度：O(|E| log |E|)

9.3 Dijkstra算法

1. 單起點最短路徑問題：對于權重連通圖的一個稱為起點的給定頂點，求出它到所有其他頂點直接的一系列最短路徑。
2. 該算法隻能應用于不含負權重的圖。
3. 首先它求出從起點到最接近起點的頂點之間的最短路徑，然後求出第二近的，以此類推。在第i次疊代開始一起，該算法已經确定了i-1條連接配接起點和離起點最近頂點之間的最短路徑。這些頂點、起點和從起點到頂點的路徑上的邊，構成了給定圖的一棵子樹Ti。因為所有邊的權重都是非負數，可以從與Ti的頂點相鄰的頂點中找到下一個和起點最接近的頂點。和Ti頂點相鄰的頂點集合稱為“邊緣頂點”，以他們為候選對象，Dijkstra算法可以從中選出下一個最接近起點的頂點。
4. 時間複雜度：O(|E| log |V|)

其他

斐波那契數列

1. 0 1 1 2 3 5 8 13 21 34 55 89……

2. F(n) = 1 n=0或1

   F(n-1) + F(n-2) n>1

3. F(n)

Procedure F(n)
	if n==0 or n==1 then
		return 1
	else return F(n-1) + F(n-2)
//指數級

Procedure F(n)
	Set A[0] = A[1] = 1
	for i = 2 to n do
		A[i] = A[i-1] + A[i-2]
	return A[n]
//時間複雜度：O(n)
           

裝配線排程