<算法导论>学习笔记(2)
Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. 是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。 1. 循环不变式的三
Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.
是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。
1. 循环不变式的三个性质:(循环不变式通常用来证明递归的正确性)
1. 初始化:它在循环的第一轮迭代开始之前,应该是正确的。
2. 保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
3. 终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。
2. 伪代码中的约定:
1. 书写上的“缩进”表示程序中的分程序(程序块)结构。
2. while,for,repeat 等循环结构和 if,then,else 条件结构与 Pascal 中相同。
3. 符号 "?”表示后面部分是个注释。
4. 多重赋值 i←j←e 是将表达式 e 的值赋给变量 i 和 j;等价于 j←e,再进行赋值 i←j。
5. 变量(如 i,j 和 key 等)是局部给定过程的。
6. 数组元素是通过“数组名[下标]”这样的形式来访问的。
7. 复合数据一般组织成对象,它们是由属性(attribute)和域(field)所组成的。
8. 参数采用按值传递方式:被调用的过程会收到参数的一份副本。
9. 布尔运算符"and”和"or”都是具有短路能力。
3. 算法分析即指对一个算法所需要的资源进行预测。
4. 对于一个算法,一般只考察其最坏情况的运行时间,理由有三:
1. 一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。
2. 对于某些算法来说,最坏情况出现得还是相当频繁的。
3. 大致上看来,“平均情况”通常和最坏情况一样差。
5. 分治策略:将原问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些小问题,然后再合并其结 果,就得到原问题的解。
6. 分治模式在每一层递归上都有三个步骤:
1. 分解(Divde):将原问题分解成一系列子问题;
2. 解决(Conquer):递归地解答各子问题。若子问题足够小,则直接求解; 3. 合并(Combine):将子问题的结果合并成原问题的解。
下面具体介绍几个知识点：
本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引入了分治（divide-and-conquer）算法策略。
1、插入排序
输入：n个数（a1,a2,a3,...,an）
输出：输入序列的一个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。
插入排序的基本思想是：将第i个元素插入到前面i-1个已经有序的元素中。具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插入到前面的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插入到前面n-1个元素中，最终使得n个元素是有序的。该算法设计的方法是增量方法。书中给出了插入排序的为代码，并采用循环不变式证明算法的正确性。我采用C语言实插入排序，完整程序如下：
void insert_sort(int *datas,int length)
{
int i,j;
int key,tmp;
//判断参数是否合法
if(NULL == datas || 0==length)
{
printf("Check datas or length.\n");
exit(1);
}
//数组下标是从0开始的，从第二个元素（对应下标1）开始向前插入
for(j=1;j=0 && datas[i] > key)
{
/×tmp = datas[i+1];
datas[i+1] = datas[i];
datas[i] = tmp;×/ 这个过程不需要进行交换，因为要插入的值保存在key中，没有被覆盖掉，在此感谢”两生花“指出问题所在
datas[i+1] = datas[i];
i--; //向前移动
}
datas[i+1] = key; //最终确定待插入元素的位置
}
}
插入排序算法的分析
算法分析是对一个算法所需的资源进行预测，资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)，最坏情况下，输入数组是按逆序排序的，时间代价为θ(n^2)。
2、归并排序
归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：
分解（divide）：将原问题分解成一系列子问题。
解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。
合并（combine）：将子问题的结果合并成原问题的解。
归并排序（merge sort）算法按照分治模式，操作如下：
分解：将n个元素分解成各含n/2个元素的子序列
解决：用合并排序法对两个序列递归地排序
合并：合并两个已排序的子序列以得到排序结果
在对子序列排序时，长度为1时递归结束，单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列，引入了一个辅助过程，merge(A,p,q,r)，将已经有序的子数组A[p...q]和A[q+1...r]合并成为有序的A[p...r]。书中给出了采用哨兵实现merge的伪代码，课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间，用来存放即将合并的有序子数组，总的空间大小为n。现在用C语言完整实现这两种方法，程序如下：
//采用哨兵实现merge
#define MAXLIMIT 65535
void merge(int *datas,int p,int q,int r)
{
int n1 = q-p+1; //第一个有序子数组元素个数
int n2 = r-q; //第二个有序子数组元素个数
int *left = (int*)malloc(sizeof(int)*(n1+1));
int *right = (int*)malloc(sizeof(int)*(n2+1));
int i,j,k;
//将子数组复制到临时辅助空间
for(i=0;i不采用哨兵实现，需要考虑两个子数组在合并的过程中哪一个先合并结束，剩下的那个子数组剩下部分复制到数组中，程序实现如下：
int merge(int *datas,int p,int q,int r)
{
int n1 = q-p+1;
int n2 = r-q;
int *left = (int*)malloc(sizeof(int)*(n1+1));
int *right = (int*)malloc(sizeof(int)*(n2+1));
int i,j,k;
memcpy(left,datas+p,n1*sizeof(int));
memcpy(right,datas+q+1,n2*sizeof(int));
i = 0;
j = 0;
for(k=p;k
merge过程的运行时间是θ(n)，现将merge过程作为归并排序中的一个子程序使用，merge_sort(A,p,r),对数组A[p...r]进行排序，实例分析如下图所示：
C语言实现如下：
void merge_sort(int *datas,int p,int r)
{
int q;
if(p
归并排序算法分析：
算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。
练习
2.1-1：以图2-2为模型，说明INSERTION-SORT在数组A=上的执行过程。
31
41
59
26
41
58
31
41
59
26
41
58
31
41
59
26
41
58
26
31
41
59
41
58
26
31
41
41
59
58
26
31
41
41
58
59
2.1-2：重写过程INSERTION-SORT，使之按非升序（而不是按非降序）排序。
INSERTION-SORT(A)
1 for j←2 to length[A]
2 do key←A[j]
3 //Insert A[j] into the sorted sequence A[1..j-1]
4 i←j-1
5 while and A[i]
6 do A[i+1] ← A[i]
7 i←i-1
7 A[i+1] ← key
2.1-3：考虑下面的查找问题：
输入：一列数A=和一个值v
输出：下标i，使得v=A[i]，或者当v不在A中出现时为NIL。
写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找v。利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。
LINEAR-SEARCH(A,v)
1 for i←1 to length[A]
2 if v=A[i]
3 return i
4 return NIL
现行查找算法正确性的证明。
初始化： i=1，子数组为A[1..i]，只有一个元素A[1],如果v=A[1]就返回1,否则返回NIL，算法显然是正确的。
保持：若算法对数组A[1..i]正确，则在数组增加一个元素A[i+1]时，只需要多作一次比较，因此显然对A[1..i+1]也正确。
终止：算法如果在非最坏情况下定能返回一个值此时查找成功，如果n次查找（遍历了所有的数）都没有成功，则返回NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明查找成功并给出下标，要么说明无此值。因此算法正确。
该算法用C#实现的代码：
public static int LinearSearch(T[] Input, T v) where T:IComparable
{
for (int i = 0; i
if (Input[i].Equals(v))
return i;
return -1;
}
2.1-4：有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。
A存放了一个二进制n位整数的各位数值，B存放了另一个同样是二进制n位整数的各位上的数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组C（n+1位）中。
BINARY-ADD(A,B,C)
1 flag← 0
2 for j←1 to n
3 do key←A[j]+B[j]+flag
4 C[j] ← key mod 2
5 if key←1
6 flag←1
7 if flag=1
8 C[n+1] ← 1
1.RAM(Random-Access Machine)模型分析通常能够很好地预测实际计算机上的性能，RAM计算模型中，指令一条接一条地执行，没有并发操作。RAM模型中包含了真实计算机中常见的指令：算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、数据移动指令（装入、存储、复制指令）和控制指令（条件和非条件转移、子程序调用和返回指令）。其中每天指令所需时间都为常量。
RAM模型中的数据类型有整数类型和浮点实数类型。
2.算法的运行时间是指在特定输入时，所执行的基本操作数（或步数）。
插入算法的分析比较简单，但是不是很有用，所以略过。（在解思考题2-1时有具体的实例分析，请参看）
3.一般考察算法的最坏情况运行时间。这样做的理由有三点：
A．一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。
B．对于某些算法，最坏情况出现的是相当频繁的。
C．大致上来看，“平均情况“通常与最坏情况一样差。
4.如果一个算法的最坏情况运行时间要比另一个算法的低，我们常常就认为它的效率更高。
练习
2.2-1：用Θ形式表示表示函数 /1000- -100n+3
Θ(n^3)
2.2-2:考虑对数组A中的n个数进行排序的问题：首先找出A中的最小元素，并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素，并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环不变式是什么?为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以 形式写出选择排序的最佳和最坏情况下的运行时间。
假设函数MIN(A,i,n)从子数组A[i..n]中找出最小值并返回最小值的下标。
SELECTION-SORT(A)
1 for i←1 to n-1
2 j←MIN(A,i,n)
3 exchange A[i]←→ A[j]
选择排序算法正确性的证明
初始化：i=1，从子数组A[1..n]里找到最小值A[j]，并与A[i]互换，此时子数组A[1..i]只有一个元素A[1]，显然是已排序的。
保持：若A[1..i]是已排序子数组。这里显然A[1] A[2] A[3] … A[i]，而A[i+1..n]里最小值也必大于A[i]，找出此最小值与A[i+1]互换并将A[i+1]插入A[1..i]得到子数组A[1..i+1]。A[1..i+1]显然也是已排序的。
终止：当i=n时终止，此时已得到已排序数组A[1..n-1]，而A[n]是经过n-1次比较后剩下的元素，因此A[n]大于A[1..n-1]中任意元素，故数组A[1..n]也即是原数组此时已是已排序的。所以，算法正确。
仅需要在头n-1个元素上运行是因为经过n-1次比较后剩下的是最大元素，其理应排在最后一个位置上，因此可以不必对此元素进行交换位置操作。
由于MIN()函数和SWAP()函数对于任意情况运行时间都相等，故这里最佳和最坏情况下运行时间是一样的。 Θ(n^2)
选择算法的的C#实现：
private static int Min(T[] Input,int start,int end) where T:IComparable
{
int flag=start;
for (int i = start; i
if (Input[flag].CompareTo(Input[i]) > 0)
flag = i;
return flag;
}
private static void Swap(ref T a,ref T b) where T
: IComparable
{
T temp;
temp = a;
a = b;
b = temp;
}
public static T[] SelectionSort(T[] Input) where T:IComparable
{
for (int i = 0; i
Swap(ref Input[Min(Input, i, Input.Length)],ref Input[i]);
return Input;
}
2.2-3：再次考虑线性查找问题（见练习2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定查找的元素是数组中任何一个元素的可能性都是相等的。在最坏情况下又怎么样呢？用Θ相似表示的话，线性查找的平均情况和最坏情况运行时间怎么样？对你的答案加以说明。
平均：n/2次。因为任意一个元素大于、小于查找数的概率一样。
最坏：n次。最后一个元素才是要查找的元素。
用Θ表示都是：Θ(n)
2.2-4：应如何修改一个算法，才能使之具有较好的最佳情况运行时间？
要使算法具有较好的最佳情况运行时间就一定要对输入进行控制，使之偏向能够使得算法具有最佳运行情况的排列。
5.分治法（divide-and-conquer）:有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的问题。这些算法通常采用分治策略：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
容易确定运行时间，是分治算法的有点之一。
6.分治模式在每一层递归上都有三个步骤：
分解（Divide）：将原问题分解成一系列子问题；
解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
7.合并排序（Merge Sort）算法完全依照了分治模式。
分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。
在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。
合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程MERGE(A,p,q,r)，其中A是个数组，p、q和r是下标，满足 。该过程假设子数组A[p..q]和A[q+1..r]都已排好序，并将他们合并成一个已排好序的子数组代替当前子数组A[p..r]。
MERGE过程的时间代价为Θ(n)，其中n=r-p+1是待合并的元素个数。
MERGE过程:
MERGE(A,p,q,r)
1 n1←q-p+n
2 n2←r-p
3 //create arrays L[1..n1+1] and R[1..n2+1]
4 for i←1 to n1
5 do L[i] ← A[p+i-1]
6 for j←1 to n2
7 do R[j] ← A[q+j]
8 L[ ] ←无穷
9 R[ ] ←无穷
10 i←1
11 j←1
12 for k←p to r
13 do if L[i]
14 then A[k] ← L[i]
15 i←i+1
16 else A[k] ← R[j]
17 j←j+1
MERGE过程正确性的证明
初始化：第一轮循环，k=p，i=1，j=1，已排序数组L、R，比较两数组中最小元素L[i]、R[j]，取较小的置于A[p]，此时子数组A[p..p]不仅是已排序的（仅有一个元素），而且是所有待排序元素中最小的。若最小元素是L[i]，取i=i+1，即i指向L中未排入A的所有元素中最小的一个；同理，j之于R数组也是如此。
保持：若A[p..k]是已排序的，由计算方法知，L中i所指、R中j所指及其后任意元素均大于等于A[p..k]中最大元素A[k],当k=k+1，A[k+1]中存入的是L[i]、R[j]中较小的一个，但是仍有A[k]
终止： k=r+1时终止跳出循环，此时，A[p..r]是已排序的，且显有A[p] A[p+1] .. A[r]。此即原待排序子数组，故算法正确。
MERGE-SORT(A,p,r)
1 if p2 then q← [(p+r)/2]
3 MERGE-SORT(A,p,r)
4 MERGE-SORT(A,q+1,r)
5 MERGE-SORT(A,p,q,r)
算法与二叉树的后序遍历算法（先左子树，然后右子树，最后根）相似。
（第三行、第四行顺序可以互换）
合并排序算法的C#实现代码：
public static void MergeSort(T[] Input,int p,int r) where T:IComparable
{
int q;
if (p
{
q = (p + r) / 2;
MergeSort(Input, p, q);
MergeSort(Input, q + 1, r);
Merge(Input,p,q,r);
}
}
private static void Merge(T[] Input,int p,int q,int r) where T:IComparable
{
int n1 = q - p + 1;
int n2 = r - q;
T[] L = new T[n1];
T[] R = new T[n2];
for (int i = 0; i
L[i] = Input[p + i];
for (int j = 0; j
R[j] = Input[q + 1 + j];
for (int i = 0, j = 0, k = p; k
{
if(i if (L[i].CompareTo(R[j])
{
Input[k] = L[i];
++i;
continue;
}
else
{
Input[k] = R[j];
++j;
continue;
}
if (i >= n1 && j
{
Input[k] = R[j];
++j;
continue;
}
if (i = n2)
{
Input[k] = L[i];
++i;
continue;
}
}
}
8.当一个算法中含有对其自身的递归调用时，其运行时间可以用一个递归方程（或递归式）来表示。
合并算法的递归式：
n