算法導論讀書筆記（1）
目錄
- 算法
- 插入排序
- 循環不變式與插入算法的正确性
- 算法分析
- 插入排序算法的分析
- 練習
- 2.1-2
- 2.1-3
- 2.1-4
- 2.2-2
算法
所謂 算法 （algorithm）就是定義良好的計算過程，它取一個或一組值作為 輸入 ，并産生出一個或一組值作為 輸出 。亦即，算法就是一系列的計算步驟，用來将輸入資料轉換成輸出結果。我們還可以将算法看作是一種工具，用來解決一個具有良好規範說明的 計算問題 。
例如，假設要将一列數按非降順序進行排列，下面是有關該排序問題的形式化定義：
輸入 ：由 n 個數構成的一個序列<a1， a2， …， an>
輸出 ：對輸入序列的一個排列（重排）<a1 '， a2 '， …， an '>使得a1 ' <= a2 ' <= … <= an '
插入排序
插入排序 算法是一個對少量元素進行排序的有效算法。它的僞碼是以一個過程的形式給出的，稱為
INSERTION-SORT
，它的參數是一個數組 A [ 1 .. n ]，包含了 n 個待排數字。（在僞碼中， A 中元素的個數 n 用 A.length 來表示。）輸入的各個數字是 原地排序 的（sorted in place），就是說這些數字是在數組 A 中進行重新排序的，在任何時刻，至多隻有其中的常數個數字是存儲在數組之外的。當過程
INSERTION-SORT
執行完畢後，輸入數組 A 中就包含了已排好序的輸出序列。
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1 .. j - 1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
插入排序算法的簡單Java實作：
/**
* 插入排序
*
* @param array
*/
public static void insertionSort(int[] array) {
int key, j;
for (int i = 1; i < array.length; i++) {
key = array[i];
j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
循環不變式與插入算法的正确性
下圖給出了這個算法在數組 A = <5， 2， 4， 6， 1， 3>上的工作過程。下标 j 訓示了待插入的元素。在外層
for
循環的每一輪疊代開始時，包含元素 A [ 1 .. j - 1 ]的子數組就已經是排好序的了。
循環不變式 主要用來幫助我們了解算法的正确性。對于循環不變式，必須證明它的三個性質：
- 初始化（Initialization）：
- 它在循環的第一輪疊代開始之前，應該是正确的。 保持（Maintenance）：
- 如果在循環的某一次疊代開始之前它是正确的，那麼，在下一次疊代開始之前，它也應該保持正确。 終止（Termination）：
- 當循環結束時，不變式給了我們一個有用的性質，它有助于表明算法是正确的。
算法分析
算法分析 是指對一個算法所需要的資源進行預測。記憶體，通信帶寬或計算機硬體等資源偶爾會是我們主要關心的，但通常，資源是指我們希望測度的計算時間。
插入排序算法的分析
INSERTION-SORT
過程的時間開銷與輸入有關。此外，即使排序兩個相同長度的輸入序列，所需的時間也可能不同。這取決于它們已排序的程度。一般來說，算法所需的時間是與輸入規模同步增長的，因而常常将一個程式的運作時間表示為其輸入的函數。這裡就涉及到兩個名詞“運作時間”和“輸入規模”。
輸入規模 的概念與具體問題有關，最自然的度量标準是輸入中的元素個數。
算法的 運作時間 是指在特定輸入時，所執行的基本操作數（或步數）。這裡我們假設每次執行第 i 行所花的時間都是常量 ci 。
首先給出
INSERTION-SORT
過程中，每一條指令的執行時間及執行次數。對 j = 2， 3， …， n ， n = A.length ，設 tj 為第5行
while
循環所做的測試次數。當
for
或
while
循環以通常方式退出時，測試要比循環體多執行1次。另外，假定注釋部分不可執行。
該算法總的運作時間是每一條語句執行時間之和。為計算總運作時間 T = [ n ]，對每一對 cost 和 times 之積求和。得：
即使是對給定規模的輸入，一個算法的運作時間也可能要依賴于給定的是該規模下的哪種輸入。例如，在
INSERTION-SORT
中，如果輸入數組已經是排好序的，那就會出現最佳情況。對 j = 2， 3， …， n 中的每一個值，都有 tj = 1，則最佳運作時間為：
這一運作時間可以表示成 a n + b ，常量 a 和 b 依賴于語句的代價 ci ；是以，它是 n 的一個 線性函數 。
如果輸入數組是按照逆序排序的，那麼就會出現最壞情況。我們必須将每個元素 A [ j ]與整個已排序的子數組 A [ 1 .. j - 1 ]中的每一個元素進行比較，因而，對 j = 2， 3， …， n ，有 tj = j 。則最壞運作時間為：
這一最壞情況運作時間可以表示為 a n2 + b n + c ，常量 a ， b 和 c 仍依賴于語句的代價 ci ；因而，這是一個關于 n 的 二次函數 。
練習
2.1-2
重寫過程
INSERTION-SORT
，使之按非升序排序。
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1 .. j - 1]
4 i = j - 1
5 while i > 0 and A[i] < key
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
2.1-3
考慮下面的查找問題：
輸入 ：一列數 A = <a1， a2， …， an>和一個值/v/ 。
輸出 ：下标 i ，使得 v = A [ i ]，或當 v 不在 A 中時為
NIL
。
寫出線性查找的僞碼：
LINEAR-SEARCH(A, v)
1 for j = 1 to A.length
2 if A[j] == v
3 return j
4 return NIL
2.1-4
将兩個各存放在數組 A 和 數組 B 中的 n 位二進制整數相加。和以二進制形式存放在具有 n + 1個元素的數組 C 中。
ADD-BINARY-ARRAY(A, B)
1 let C[1 .. A.length + 1] be new arrays
2 flag = 0
3 for i = 1 to A.length
4 key = A[i] + B[i] + flag
5 C[i] = key mod 2
6 if key > 1
7 flag = 1
8 else
9 flag = 0
10 C[i] = flag
2.2-2
選擇排序 僞碼：
SELECT-SORT(A)
1 for i = 1 to A.length - 1
2 index = i
3 for j = i + 1 to A.length
4 if A[index] > A[j]
5 index = j
6 exchange A[index] with A[i]
轉載于:https://www.cnblogs.com/sungoshawk/p/3617652.html