【算法导论】第2章 算法基础

@TOC

2.1-1 说明INSERTION-SORT在数组A= 31,41,59,26,41,58 上的执行过程。

a. 31,41,59,26,41,58

b. 31,41,59,26,41,58
c. 31,41,59,26,41,58
d. 26,31,41,59,41,58
e. 26,31,41,41,59,58
f. 26,31,41,41,58,59

2.1-2 重写过程INSERTION-SORT，使之按非升序排序。

for i=2 to A.length

 key = a[i]

 j = i - 1

 while j 0 and a[j] key

 A[j+1] = A[j]

 j = j - 1

 A[j+1] = key

2.1-3 考虑以下查找问题：
输入：n个数的一个序列A= a1,a2,a3,...,an 和一个值v。
输出：下标i使得v=A[i]或者当v 不在A中出现时，v为特殊值NIL。

for i=1 to n

 if v = A[i]

 return i;

 return NIL;

证明循环不定式成立：

 初始化：迭代之前，其子数组为空，没有找到继续循环，循环不定式成立。

 保持：如果A[1...i-1]不包含v，我们比较A[i]与v。相等则返回i，不等则进行下一步。

 终止：i A.length，则A中肯定不包含v，返回NIL。

2.1-4 把两个n为二进制整数加起来，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按照二进制形式存储在一个（n+1）元数组C中。

ADD_BINARY(A,B):

 C = new integer[A.length + 1]

 temp = 0

 for i=1 to A.length

 C[i] = (A[i] + B[i] + temp) % 2

 temp = (A[i] + B[i] + temp) / 2

 C[i+1] = temp

 return C

@TOC

2.2-1 表示函数n^3 / 1000 - 100n^2 -100n + 3。

n^3 / 1000 - 100n^2 -100n + 3 = O(n^3)

2.2-2 写出选择排序算法的伪代码。该算法维持的循环不定式是什么？为什么只需要对前n-1个元素，而不是对所有n个元素运行？给出选择排序的最好情况和最坏情况运行时间。

SELECT_SORT(A,n):

 for i=0 to n-1

 min = i

 for j=i+1 to n

 if A[j] A[min]

 min = j

 if min != j

 swap(A[i],A[min]) //交换A[i]和A[min]

证明循环不定式成立：

 初始化：迭代之前，子数组为空，循环不定式成立。

 保持：当迭代至第 i 时，子数组A[1,...,i-1]已按序排列，for循环的下一次迭代增加i将保持循环不定式。

 终止：当i迭代至i=n-1时，A[1-n]都按序排列。

 

每次迭代都是找出A[i-n]中的最小元素，在经过n-1次后，剩下的最后一个元素一定为A中的最大元素。

最好情况与最坏情况均为O(n^2)

2.2-3 再次考虑现行查找问题（练习2.1-3）。假定要查找的元素等可能的为数组中的任意元素，平均需要检查输入序列的多少元素？最坏元素又如何？

平均：待查找的元素等概率出现（概率为：1/n）：（1 + 2 + 3 + ... + n）/ n = (n+1) / 2
最坏：n
运行时间均为：O(n)

2.2-4 应如何修改任何一个算法，才能使之具有良好的最好情况运行时间？

在算法中加入对最好情况的判断。例如：排序时，如果输入序列已经排好序，则直接return，这样最好情况运行时间为O（n）。

@TOC

2.3-1 说明并归排序在数组A = 3,41,52,26,38,57,9,49 上的操作。

2.3-2 重写过程MERGE，使之不使用哨兵，而是一旦数组L或R的所有元素均被复制回A就立刻停止，然后把另一个数组的剩余部分赋值回A。

MERG(A,p,q,r):

 n1 = q-p+1

 n2 = r-q

 for i = 1 to n1

 L[i] = A[p+i-1]

 for j = 1 to n2

 R[j] = A[q+j}

 temp = 1

 for k1 = p to q and k2 = q+1 to r

 if L[k1] = L[k2]

 A[temp] = L[k1]

 temp = temp + 1

 else

 A[temp] = L[k2]

 temp = temp + 1

 while(k1 = q)

 A[temp++] = L[k1++]

 while(k2 = r)

 A[temp++] = R[k2++]

2.3-3使用数学归纳法证明：当n刚好是2的幂时，一下递归式的解是T(n)=nlgn。
T(n)=2，若n=2
T(n)=2T(n/2)+n, 若n=2^k,k 1

2.3-4 我们可以把插入排序表示为如下的一个递归过程。为了排序A[1..n]，我们递归地排序A[1..n-1]，然后把A[n]插入已排序的数组A[1..n-1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。

2.3-5 回顾查找问题(参见练习2.1-3)，注意到，如果序列A已排好序，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为O(lgn)。

BINARY_SEARCH(A，key,p.r):

 if mid = r and key != A[p]

 return NIL

 j = (r-p) / 2

 if key = A[j]

 return j;

 else

 if key A[j]

 return BINARY_SEARCH(A,key,p,j)

 else

 return BINARY_SEARCH(A,key,j,r)

// T(n) = O(lgn)

2.3-6 注意到2.1节中的过程 INSERTION-SORT 的第5~7行的while循环采用一种线性查找来(反向)扫描已排好序的子数组A[1..j-1]。我们可以使用二分查找(参见练习2.3-5)来把插入排序的最坏情况总运行时间改进到O(nlgn)吗?

INSERTION_SORT:

 for i=2 to A.length

 key = A[i]

 low = 1 

 high = i-1

 while low = high

 mid = (low + high) / 2

 if key = A[mid]

 break

 else if key A[mid]

 high = mid- 1

 else

 low = mid + 1

 for j = mid to i-1

 A[j+1] = A[j]

 A[mid] = key

在最坏情况下，二分查找的时间复杂度为nlgn，但元素的移动次数未改变，它依赖于待排序表的初始状态，因此总运行时间不能改进到O(nlgn)，仍然为O(n^2)。

2.3-7 描述一个运行时间为O(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。

（1）将集合S排序（并归排序） O(lgn)
（2）循环折半查找 x-A[i]，存在 return true；不存在 return false

CHECK_SUMS(A,x):

 SORT(A)

 for i = 1 to A.length

 if BINARY_SEARCH(A,x-A[i],i,n)

 return true

@TOC

2-1 (在归并排序中对小数组采用插入排序）虽然归并排序的最坏情况运行时间为O(n lgn)，而插人排序的最坏情况运行时间为O(n^2)，但是插入排序中的常量因子可能使得它在n较小时，在许多机器上实际运行得更快。因此，在归并排序中当子问题变得足够小时，采用插人排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为k的n/k个子表，然后使用标准的合并机制来合并这些子表，这里k是一个待定的值。
**a. 证明:插入排序最坏情况可以在O(nk)时间内排序每个长度为k的n/k个子表。
b. 表明在最坏情况下如何在O(nlg(n/k))时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为O(nk十nlg(n/k))，要使修改后的算法与标准的归并排序具有相同的运行时间，作为n的一个函数，借助O记号，k的最大值是什么?
d. 在实践中，我们应该如何选择k?**

a. 插入排序最坏运行时间为O(n^2)，即 ak^2 + bk + c；
n/k个子表共需：n/k(ak^2 + bk + c) = ank + bn + nc/k = O(nk)；

b. 并归排序时递归树树高为：lg(n/k)，每个叶子代价为ck
合并的总代价为O(ck(n/k)lgn/k) = O(nlgn/k)

c. O(nk + nlgn/k) = O(nlgn)，即k = lgn，k的最大值为lgn

d. 选择的k值应使插入排序快于并归排序

**2-4 (逆序对）假设A_1..n]是一个有n个不同数的数组。若i j且Ai Aj]，则对偶(i，j)称为A的一个逆序对(inversion)。
a. 列出数组(2，3，8，6，1 的5个逆序对。
b. 由集合{1，2，…，n)中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
c. 插人排序的运行时间与输人数组中逆序对的数量之间是什么关系?证明你的回答。**

a. 2,1 , 3,1 , 8,1 , 6,1 , 8,6
b. 当集合降序排列时，具有最多的逆序对，共有n(n-1)/2对。
c. 逆序对的数量决定while内循环的执行次数。

算法基础学习2——冒泡排序 要比较的每一对元素是相邻的，从下标为0开始，到最后一个元素，如果下标设为 j，则相邻元素下标值为 j +1，搜索到最后一个元素：j+1 a.length，而 a.length - 1 = i ；所以终止条件是 j i
算法基础STL C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。
【算法基础】希尔排序解析 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时，再对全体记录进行依次直接插入排序。
【算法基础】冒泡排序解析 在我们数组排序中，每一个数组元素根据大小比对，小的元素不断向前移动，如同气泡在冒出一样，我们称这种排序方法为冒泡排序。
【算法基础】归并排序解析 归并排序是建立在归并操作上的一种有效，稳定的排序算法，它是采用分治法的一个非常典型的应用。将待排序数组分为两条线逐级拆分，将子序列进行排序，然后沿两条线逐级合并，得到完全有序序列。这种通过递归，层层合并的方法，称为归并。
算法基础 递归算法在计算机系统中用栈帮助实现，一般常见的算法有深度优先遍历（DFS），可以解决的问题有迷宫问题是否连通的问题，递推会对应一个递归搜索树，递归搜索树可以帮助我们更好的理解递归的流程，递归要注意的有是否可以进行剪枝，在迷宫问题中，也要考虑是否要保存原有的迷宫。