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

• 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 分析算法)

• 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 设计算法)

• 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内循环的执行次数。