Chapter 2
插入排序
线性查找
选择算法
归并排序算法
二分查找算法
冒泡排序
插入排序
INSERTION-SORT(A)
for j=2 to A.length
key = A[j]
//insert A[j] into the sortes sequence A[1...j-1]
i = j-1
while i>0 and A[i]>key
A[i+1] = A[i]
i = i-1
A[i+1] = key
function insertion_sort(arr) {
var key = 0;
var i = 0;
for(var j = 1; j < arr.length; j++) {
key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] > key) {
arr[i+1] = arr[i];
i = i - 1;
}
arr[i+1] = key;
}
return arr;
}
循环不变式
初始化：循环第一次迭代之前，它为真
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的
算法分析
| INSERTION-SORT(A) | 代价 | 次数 |
|---|---|---|
| for j=2 to A.length | c1 | n |
| key = A[j] | c2 | n-1 |
| //insert A[j] into the sortes sequence A[1...j-1] | 0 | n-1 |
| i = j-1 | c4 | n-1 |
| while i>0 and A[i]>key | c5 | ∑tj (2<=j<=n) |
| A[i+1] = A[i] | c6 | ∑(tj - 1) (2<=j<=n) |
| i = i-1 | c7 | ∑(tj - 1) (2<=j<=n) |
| A[i+1] = key | c8 | n-1 |
tj 表示对那个值j第5行执行while循环测试的次数
所以，T(n) = c1n + c2(n-1) + c4(n-1) + c5∑tj (2<=j<=n) + c6∑(tj - 1) (2<=j<=n) + c7∑(tj - 1) (2<=j<=n) + c8(n-1)
最佳情况：对j=2, 3, ..., n，有tj = 1，所以 T(n) = (c1 + c2 + c4 + c5 +c8)n - (c2 + c4 + c5 + c8) = Θ(n)
最坏情况：对j=2, 3, ..., n，有tj = j，所以 ∑tj (2<=j<=n) = ∑j (2<=j<=n) = n(n+1)/2 - 1, ∑(tj - 1) (2<=j<=n) = n(n-1)/2, T(n) = (c5 + c6 + c7)n^2/2 + (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8)n - (c2 + c4 + c5 + c8) = Θ(n^2)
分治模式
分治模式在每层递归时都有三个步骤：
分解原问题为若干个子问题，这些字问题是原问题的规模较小的实例。
解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
合并这些子问题的解成原问题的解。
归并排序算法
归并排序算法完全遵循分治模式。直观上其操作如下：
分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
解决：使用归并排序递归地排序两个子序列。
合并：合并两个已排序的子序列以产生已排序的答案。
通过调用一个辅助过程MERGE(A, p, q, r)来完成两个已排序序列的合并，其中A是一个数组，p、q和r是数组下标，满足 p<=q<r。该过程假设子数组A[p..q]和A[q+1..r]都已排好序。它合并两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r]。
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
Let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q+j]
//插入哨兵牌
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
MERGE-SORT(A, p, r)
if p < r
q = └(p + r)/2┘
MERGE-SORT(A, p, q)
MERGE-SORT(A, q + 1, r)�
MERGE(A, p, q, r)
分析分治算法
分治算法运行时间的递归式来自基本模式的单个步骤。假设T(n)是规模为n的一个问题的运行时间。若问题规模足够小，如对某个常量c，n<=c，则直接求解需要常量时间，将其记作Θ(1)。假设把原问题分解成a个子问题，每个子问题的规模是原问题的1/b。为了求解一个规模为n/b的子问题，需要T(n/b)的时间，所以，需要aT(n/b)的时间来求解a个子问题，如果分解问题成子问题需要时间D(n)，合并子问题的解成原问题的解需要C(n)，那么得到递归式：
若n<=c，T(n) = Θ(1)；其他，T(n) = aT(n/b) + D(n) + C(n)
所以，归并排序的最坏情况运行时间T(n)的递归式：
若n=1，T(n) = Θ(1)；若n>1，T(n) = 2T(n/2) + Θ(n)
等价于：若n=1，T(n) = c；若n>1，T(n) = 2T(n/2) + cn
对递归式T(n) = 2T(n/2) + cn构造递归树，如下：
的霍纳规则。
a. 借助Θ记号，实现霍纳规则的以上代码片段的运行时间是多少？
b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？
c. 考虑以下循环不变式：
在第2～3行for循环每次迭代的开始有
把没有项的和式解释为等于0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有
d. 最后证明上面给出的代码片段将正确地求由系数a0, a1, …, an刻画的多项式的值。
a. Θ(n)
b. 伪代码如下：
y = 0
tmp = 1
for k = 0 to n
y = y + ak * tmp
tmp = tmp * x
该算法的时间复杂度为：Θ(n^2)
c. 证明如下：
初始化：i=n时，y=0
保持：对于任意 0 ≤ i ≤ n，迭代的开始有y=Σ a[k+i+1] * x^k =a[k+i+1] + a[k+i+2] * x + ... + an * x^(n-(i+1))，循环后有：y[i] = a[i] + y[i+1] * x = a[i] + (a[i+1] * x + a[i+2] * x + ... + a[n] * x^(n-(i+1))) * x = a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i)
终止：i=0时，循环终止，i=0开始前有y=Σ a[k+1] * x^k = a[1] + a[2] * x + a[n] * x^(n-1)，执行循环，y=a0 + x * [a[1] + a[2] * x + a[n] * x^(n-1)] = a0 + a[1]x + a[2]x^2 + ... + a[n]*x^n。
d. <我并没有看懂>
Answer2-3d.png
2.4 （逆序对）假设A[1..n]是一个有n个不同数的数组。若i < j且A[i] > A[j]，则对偶(i, j)称为A的一个逆序对(inversion)。
a. 列出数组 <2, 3, 8, 6, 1> 的5个逆序对。
b. 由集合 {1, 2，…，n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？
c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。
d. 给出一个确定在n个元素的任何排列中逆序对数量的算法，最坏情况需要 Θ(nlgn) 时间。（提示：修改归并排序。）
a. (2, 1), (3, 1), (8, 6), (8, 1), (6, 1)
b. <n, n-1, n-2, ..., 1>拥有最多的逆序对，共有 n*(n-1)/2
c. 逆序对越多，插入排序的复杂度越大
排序n个数，如果不存在逆序对，则插入排序的复杂度为Θ(n)，每多一个，复杂度加1
d. 如下：
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
Let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q+j]
//插入哨兵牌
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
count = 0
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
count = count + 1
网友评论