第一章 算法在计算中的作用
习题
1.2-2
假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并排序?
解：
建立不等式：8n^2 < 64nlog_2n
化简：n < 8log_2n
取不等式的正整数解，即n = 2, 3, ... , 43时，插入排序由于归并排序。
第二章 算法基础
插入排序
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
i = j-1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key循环不变式的三条性质
初始化：循环的第一次迭代之前，它为真。
保持：每次循环迭代完成之后，在下次迭代开始之前它依旧保持为真。
终止：在循环终止后，该不变式为我们提供一个有用的性质，能够帮助证明算法的正确性。
例题2.2-4
我们可以如何修改几乎任意算法来使之具有良好的最好情况运行时间？
首先判断输入是否属于最好情况，判断成功则不进行后续操作。
归并排序
MERGE(A, p, q, r)
n1 = q-p+1
n2 = r-q
let L[1..n1+1], 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] = INF
R[n2+1] = INF
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)递归树
习题
2.1-1
说明INSERTION-SORT在数组A=〈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-DESC(A):
for j = 2 to A.length
key = A[j]
i = j-1
while i > 0 and A[i] < key
A[i+1] = A[i]
i = i-1
A[i+1] = key2.1-3
考虑以下查找问题:
输入:n个数的一个序列A=[a1，a2 ,…，an]和一个值v。
输出:下标i使得v=A[i]或者当v不在A中出现时，v为特殊值NIL。
写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。
解：
LINEAR-SEARCH(A, v):
ans = NIL
for i = 1 to A.length
if A[i] == v
ans = i
return ans初始化：循环开始之前，ans为NIL。
保持：如果找到v，ans会被赋值为i。输出是正确的。
终止：如果没有找到v，ans会保持初始值为NIL；如果找到，ans已经在循环中被赋值为i。算法正确。
2.1-4
考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个(n+1)元数组C中。请给出该问题的形式化描述,并写出伪代码。
解：
BIT-ADD(A, B):
carry = 0
let C[1..n+1] be a new Array
for i = n downto 1:
tmp = A[i]+B[i]+carry
carry = 0
if tmp >= 2:
carry = 1
tmp = tmp - 2
C[i+1] = tmp
C[1] = carry
return C2.2-1
用\Theta记号表示函数\frac{n^3}{1000} - 100n^2 - 100n + 3
解：
\Theta (n^3)
2.2-2
考虑排序存储在数组A中的n个数:首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素并将其与A[2]中的元素进行交换。对A中前n一1个元素按该方式继续。该算法称为选择算法，写出其伪代码。该算法维持的循环不变式是什么?为什么它只需要对前n-1个元素，而不是对所有n个元素运行?用记号给出选择排序的最好情况与最坏情况运行时间。
解：
SELECTION-SORT(A):
for i = 1 to n-1
for j = i+1 to n
if A[j]<A[i]
exchange A[i] with A[j]循环不变式：
在第i次循环时，A[1]是第1小的数，A[2]是第2小的数...A[i-1]是第i-1小的数。
证明：
初始化：在进入循环之前，A[1..i-1]有序，且保证A[1]是第1小的数，A[2]是第2小的数...A[i-1]是第i-1小的数。
保持：内层循环从A[i+1]开始，逐个与A[i]比较，如果比A[i]小，则与A[i]交换位置。因此内层循环结束后，能保证A[i]是A[i...n]中最小的数。
又因为任取j \in {1,...,i-1}，有A[j] \leqslant A[i]，所以A[i]是A中第i小的数。循环不变式保持。
终止：当 i>n-1 时，循环终止。此时A[1..n-1]有序，且保证A[1]是第1小的数，A[2]是第2小的数...A[n-1]是第n-1小的数。
由上述结论，任取j \in {1,...,n-1}，有A[j] \leqslant A[n]，所以A[n]是A中第n小的数。
综合上述三条性质，得出：在表A中，设n=A.length，A[i](i \in {1,2,...,n})总是A中第i小的数。也就是表A中元素升序排列。
据数学归纳法证明得知，此算法的外层第i次循环保证了A[i]元素是所有元素中第i小的；循环至n-1次时，A[1]是第1小的数，A[2]是第2小的数...A[n-1]是第n-1小的数；假设A[n]需要移动，那么A[n]就不是A中第n小的数，与上述结论矛盾；所以无需对A[n]进行比较。
最好情况：O(n)；最坏情况：O(n^2)。
2.2-3
再次考虑线性查找问题(参见练习2.1-3)。假定要查找的元素等可能地为数组中的任意元素，平均需要检查输入序列的多少元素?最坏情况又如何呢?用\Theta记号给出线性查找的平均情况和最坏情况运行时间。证明你的答案。
解：
平均需要检查\frac{n}{2}个，最坏情况检查n个。因此拥有渐进紧确界\Theta (n)。
2.3-1
说明归并排序在数组A=[3，41，52，26，38，57，9，49]上的操作。
解：
分：
[3,41,52,26] [38,57,9,49]
[3,41] [52,26] [38,57] [9,49]
排：
[3,41] [26,52] [38,57] [9,49]
合：
[3,26,41,52] [9,38,49,57]
[3,9,26,38,41,49,52,57]
2.3-2
重写过程 MERGE，使之不使用哨兵，而是一旦数组L或R的所有元素均被复制回A就立刻停止，然后把另一个数组的剩余部分复制回A。
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 n
L[i] = A[p+i-1]
for j = 1 to n
R[j] = A[q+j]
i = 1
j = 1
cnt = 0;
times = min(n1, n2)
for k = p to r
if cnt > times
if L[i].exist()
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
else
cnt = cnt + 1
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 12.3-3
使用数学归纳法证明：当n刚好是2的幂时，以下递归式的解是T(n)=nlgn。
T(n)=2 (n=2), T(n) = 2T(n/2)+n（n=2^k, k>1）
解:
令x=2^k, k=1,2,3...
当k=1时，T(x)=2lg2=2，得证；
当k=2时，T(x)=2T(2)+4=8=4lg4，得证；
假设k=i时，T(x)=2T(x/2)+2^i=2^ilg2^i = i2^i, i>2，则k=i+1时，T(x)=2T(x/2)+2·2^i=2i2^i+2^{i+1}=(i+1)2^{i+1} = 2^{i+1}lg2^{i+1}，证毕。
2.3-4
我们可以把插入排序表示为如下的一个递归过程。为了排序 A[1..n]，我们递归地排序A[1..n—1]，然后把A[n]插入已排序的数组A[1..n-1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。
解：
T(1) = 1; T(n) = T(n-1) + n;
2.3-5
回顾查找问题(参见练习2.1-3)，注意到，如果序列A已排好序，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为\Theta (lgn)。
解：
BINARY-SEARCH(A, l, r, v)
if l >= r
return l
else
mid = (l+r)//2
if A[mid] == v
return mid
else
if A[mid] > v
return BINARY-SEARCH(A, l, mid-1, v)
else
return BINARY-SEARCH(A, mid+1, r)关于mid的奇偶需要微调，不过大体就是上面的代码。
设数据规模为n，每次递归在常数时间将查找规模缩小一半，构建递归式:T(n) = T(n/2) + c，应用主定理得T(n) = \Theta(lgn)
2.3-6
是否可以用二分查找法把插入排序最坏条件下运行时间改善到 Θ(nlgn)？
解:
不可以。插入操作需要的时间复杂度还是\Theta (n)。
2.3-7
描述一个运行时间为\Theta (nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。
解：
用时间复杂度为\Theta (nlgn)的排序算法将集合S排序。然后新建一个数组S1，使得S1[i] = x – S[i]，再将两个数组并起来。如果存在两个连续的相等值，也就是y1,y1,...,y2,y2 且y1+y2 = x，则可以确定S中存在有两个其和等于x的元素。
或者排序后，定义两个指针，指向集合首尾。如果指针指向的元素和为x，返回true。如果小于x，首指针加1，如果大于x，尾指针减1。如果首指针和尾指针重合，还没有找到x，返回false。
思考题
2-1
(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为\Theta (nlgn)，而插入排序的最坏情况运行时间为\Theta(n^2)，但是插入排序中的常量因子可能使得它在n较小时，在许多机器上实际运行得更快。因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为k的n/k个子表，然后使用标准的合并机制来合并这些子表，这里k是一个待定的值。
a. 证明:插入排序最坏情况可以在\Theta (nk)时间内排序每个长度为k的n/k个子表。
b. 表明在最坏情况下如何在\Theta (nlg(n/k))时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为\Theta (nk+nlg(n/k))，要使修改后的算法与标准的归并排序具有相同的运行时间，作为n的一个函数，借助\Theta记号，k的最大值是什么?
d. 在实践中,我们应该如何选择k?
解：
a. 插入排序的时间复杂度为\Theta (n^2)，如果长度为k，共有n/k个子表，根据\Theta记号的定义，这一算法的时间复杂度可以表示为(n/k)T(k) = c\frac{n}{k}k^2+o(k) = cnk+o(k) = \Theta (nk)。
b. 画出递归树可以看到这颗树的深度为lg(n/k)
每一层的规模都是n，所以对每一层调用MERGE过程的最坏情况运行时间都是\Theta(n)
所以，对于lg(n/k)层的树，最坏情况运行时间总共为\Theta(nlg(n/k))。
c. c_1nk+c_1nlg(n/k) = c_2nlgn
c_1k+c_1lg(n/k) = c_2lgn = c_1k+c_1lgn-c_1lgk = \Theta (lgn)；因此k有上界O(lgn)。
d. 选择k=\Theta(lgn)。
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.在 Θ(nlgn) 的最坏情况运行时间，确定n个元素任何排列中的逆序对数目。
解：
a. (2,1) (3,1) (8,6) (8,1) (6,1)；
b. 降序排列的数组具有最多的逆序对，数量为$\frac{n(n-1)}{2}$；
c. 设R(n)为逆序对数量，它与运行时间T(n)的关系是：T(n)=O(R(n))；
接下来用数学归纳法证明上述关系：
1) n=2，显然成立;
2) 设n=k(k>2)，关系成立，则T(k)=O(R(k))。n=k+1时，R(k+1)=R(k)+R_p(k+1)，这里的R_p(k+1)是关于第k+1个元素的逆序对数量。
先令前k个元素有序，T(k)=O(R(k))，再将第k+1个元素插入到合适的位置，在这一步中，前k个元素插入到合适的位置，在这一步中，
有R_p(k+1)个元素大于此元素，所以运行时间为O(R_p(k+1))。将二步的运行时间相加，
得T(k+1)=O(R(k))+O(R_p(k+1))=O(R(k+1))。
证毕。
d. 归并排序，在合并的步骤中，如果A数组指针指向的元素大于B数组指针指向的元素，逆序对数+1。最后归并排序结束后可以得到答案。
第三章 函数的增长
渐进记号
\Theta记号
\exist c_1, c_2, n_0，当n>n_0时，对函数f(n), g(n)，有c_1g(n) \leqslant f(n) \leqslant c_2g(n)，则称“f(n) = \Theta (g(n))”。
O记号
\exist c, n_0，当n>n_0时，对函数f(n), g(n)，有f(n) \leqslant cg(n)，则称“f(n) = O(g(n))”。
\Omega记号
\exist c, n_0，当n>n_0时，对函数f(n), g(n)，有f(n) \geqslant cg(n)，则称“f(n) = O(g(n))”。
不是所有的函数都可以渐进比较，有可能f(n) = O(g(n)), f(n) = \Omega(g(n))同时不成立，比如n，n^{1+sinn}。
习题
3.1-1
假设f(n)与g(n)都是渐近非负函数。使用\Theta记号的基本定义来证明max(f(n)，g(n))=\Theta (f(n)＋g(n))。
解：
由于函数非负，
cmax(f(n),g(n)) \leqslant cf(n)+cg(n)
然后需要证明：\exist c_1, c_2 > 0，c_1max(f(n), g(n)) \geqslant c_2f(n)+c_2g(n)
不妨假设\exist N>0，对每个n>N，有f(n) \geqslant g(n)，上述等式可以化为c_1f(n)-c_2f(n)-c_2g(n) \geqslant 0；
放缩等式c_1f(n)-c_2f(n)-c_2g(n) \geqslant c_1f(n)-2c_2f(n)；
只要c1 \geqslant 2c_2，就有上述等式大于等于0恒成立。
证毕。
3.1-2
证明:对任意实常量α和b，其中b>0，有(n+a)^b = \Theta (n^b)
解：
不妨假设a非负，(n+a)^b \geqslant n^b；
只要证明\exist c_1, c_2 > 0, c_1(n+a)^b \leqslant c_2n^b。
移项变形后得到(c_1-c_2)n^b + o(n^b-1)，只要c_2 - c_1足够大，就有(c_1-c_2)n^b + o(n^b-1) \leqslant 0。
证毕。
3.1-3
解释为什么“算法A的运行时间至少是O(n^2)”这一表述是无意义的。
解：
T(n) \geqslant O(n^2)，对于函数f(n) = 0，有f(n) \leqslant n^2, f(n) = O(n^2)，T(n) \geqslant f(n)无意义。
第四章 分治策略
分治策略在每层递归中应用如下三个步骤：
分解步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决步骤递归地求解子问题，如果子问题地规模足够小，则停止递归，直接求解。
合并步骤将子问题的解组合成原问题的解。
求解递归式
代入法
猜测一个界，使用数学归纳法证明它是正确的。
求解递归式:T(n) = T(n − 2) + 2 lg n;
解：假设T(n)=O(nlgn)且T(1)=1是递归式唯一的边界条件。当n=3时，易得T(3) = T(1) + 2lg3 = 1+2lg3 \leqslant 3lg3。令n_0=3，设k>n_0，选择常数c>0，有T(k) = T(k-2) + 2lgk \leqslant cklgk，T(k-2) \leqslant c(k-2)lg(k-2)；T(k) \leqslant c(k-2)lg(k-2)+lgk \leqslant cklgk只要c \geqslant 1，上式均能成立。所以存在n_0 = 3，对每个n>n_0，有T(n) = O(nlgn)。
主定理
令a \geqslant 1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式：T(n) = aT(\frac{n}{b}) + f(n)。
其中我们将\frac{n}{b}解释为下取整或者上取整。那么T(n)有如下渐进界：
1.若对某个常数\epsilon > 0有 f(n) = O(n^{log_{b}a-\epsilon })，则T(n) = \Theta(n^{log_ba})。
2.若f(n) = \Theta(n^{log_ba})，则T(n) = \Theta (n^{log_ba}lgn)。
3.若对某个常数\epsilon > 0有f(n) = \Omega(n^{log_ba-\epsilon})，且对某个常数c<1和足够大的n有af(\frac{n}{b}) \leqslant cf(n)，则T(n) = \Theta(f(n))。
最大子数组问题
给定数组A，求最大连续元素之和。
分治法。跨越mid的数组容易求。然后分治左右两侧的情况。
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -inf
sum = 0
for i = mid downto low
sum = sum+A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -inf
sum = 0
for j = mid+1 to high
sum = sum+A[j]
if sum > right-sum
right-sum = sum
max-right = j
return(max-left, max-right, left-sum+right-sum)FIND-MAX-SUBARRAY(A, low, high)
if high == low
return(low, high, A[low])
else
mid = (low+high)/2
(left-low, left-high, left-sum) = FIND-MAX-SUBARRAY(A, low, mid)
(right-low, right-high, right-sum) = FIND-MAX-SUBARRAY(A, mid+1, high)
(cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
return max(left-sum, right-sum, cross-sum)Strassen矩阵乘法
将矩阵分块。
[r][s] = [a][b] · [e][f]
[t][u] [c][d] [g][h]
p1 = a( f - h )
p2 = ( a + b )h
p3 = ( c +d )e
p4 = d( g - e )
p5 = ( a + d )( e + h )
p6 = ( b - d )( g + h )
p7 = ( a - c )( e + f )
那么只需要计算p1,p2,p3,p4,p5,p6,p7，然后
r = p5 + p4 + p6 - p2
s = p1 + p2
t = p3 + p4
u = p5 + p1 - p3 - p7
最终达到降低复杂度为O( n^lg7 ) ~= O( n^2.81 );
换元技巧
思考题4-4
解：
a. z+zF(z)+z^2F(z) = z+z^2+z^3+2z^4+...+z^3+z^4+... = z+z^2+2z^3+3z^4+... = F(z)
b. 由上式变形，分母因式分解可得。
c. 将大括号内的分式按照等比级数展开即可。
d. F_i < 0.5，任意数减去一个小于0.5的数，舍入到最接近的整数。
第六章 堆排序
堆排序
MAX-HEAPIFY
维护最大堆性质的函数，我们假定根节点LEFT(i)和RIGHT(i)的二叉树都是最大堆。但A[i]可能小于其孩子。MAX-HEAPIFY函数通过让A[i]的值逐级下降，使得下标为i的节点的树重新遵循最大堆的性质。
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap_size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap_size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)BUILD-MAX-HEAP
采用自底向上的方式建立大顶堆，对每个节点调用一次MAX-HEAPIFY函数即可。由于A[n/2+1..n]中的元素都是叶子节点，所以可以跳过这些节点。
BUILD-MAX-HEAP(A)
A.heap_size = A.length
for i = A.length/2 downto 1
MAX-HEAPIFY(A, i)渐进紧确界
简单估算，每次调用MAX-HEAPIFY函数的时间复杂度是O(lgn)，n次调用，所以总时间复杂度为O(nlgn)。
这个上界虽然正确，但不是渐进紧确的。
观察得到，不同节点运行MAX-HEAPIFY的时间与该节点的高度相关。并且大部分的节点高度较小（高度较小的节点靠树的下端，每层容量翻倍）。
因此通过如下结论：
- 包含n个元素的堆，高度为
\lfloor lgn \rfloor - 高度为h的堆最多包含
\lceil \frac{n}{2^{h+1}} \rceil个节点
可以得到总代价的表达式：
堆排序伪代码
HEAPSORT(A):
BUILD_MAX_HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap_size = A.heap_size - 1
MAX_HEAPIFY(A, 1)优先队列
最大优先队列支持以下操作：
- INSERT(S, x) 将元素x插入S
- MAXIMUM(S) 返回S中最大关键字的元素
- EXTRACT_MAX(S) 去除并返回S中最大关键字的元素
- INCREASE_KEY(S, x, k) 将第x个元素的关键字增加到k，预设k的值大于等于x的关键字值
习题
6.1-1
在高度为h的堆中，元素个数最多和最少分别是多少?
解：
最多2^{h+1}-1个，最少2^{h}个。（根节点高度为0）
6.1-2
证明:含n个元素的堆的高度为\lfloor lgn \rfloor。
解：
由于堆除了最后一层是一个满二叉树。根据满二叉树的性质，2^h \leqslant n \leqslant 2^{h+1}-1, h \leqslant lgn \leqslant lg(2^{h+1}-1)，可得题述结论。
6.1-7
证明：用数组表示存储n个元素的堆时，叶节点下标分别是\lfloor n/2 \rfloor +1, \lfloor n/2 \rfloor +2, ..., n。
解：
据题设，由堆的构建方法得知，下标为n的节点必是叶子节点。
又因为除底层外，堆的每一层都是从左至右完全充满的。
根据完全二叉树的性质，可以由n找到最近的一个父节点\lfloor n/2 \rfloor。
接下来用反证法证明上述结论：
假设距离n最近的父节点下标为\lfloor n/2 \rfloor +1，则根据二叉树的建立方式，
它的左子节点下标为2*(\lfloor n/2 \rfloor +1) > n，即左子节点不存在，与它是父节点相矛盾。
因此，由完全二叉树的性质，堆的叶子节点的下标为\lfloor n/2 \rfloor +1, \lfloor n/2 \rfloor +2, ... , n。
6.2-2
参考过程 MAX-HEAPIFY，写出能够维护相应最小堆的MIN-HEAPIFY(A，i)的伪代码，并比较 MIN-HEAPIFY 与 MAX-HEAPIFY的运行时间。
MIN-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] < A[i]
smallest = l
else smallest = i
if r <= A.heap-size and A[r] < A[smallest]
smallest = r
if smallest != i
exchange A[i] with A[smallest]
MIN-HEAPIFY(A, smallest)运行时间相同。均为O(lgn)。
6.2-3
当元素A[i]比其孩子的值都大时，调用MAX-HEAPIFY(A.i)会有什么结果?
解：
在O(1)时间内终止。
6.2-5
MAX-HEAPIFY的代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译器产生低效的代码。请用循环控制结构取代递归，重写MAX-HEAPIFY代码。
解：
MAX-HEAPIFY(A,i)
while true
l=LEFT(i)
r=RIGHT(i)
largest=i
if l<=A.heap-size and A[l]>A[i]
largest=l
if r<=A.heap-size and A[r]>A[i]
largest=r
if largest=i
break
else
exchange A[i] with A[largest]
i=largest6.4-3
对于一个按升序排列的包含n个元素的有序数组A来说，HEAPSORT的时间复杂度是多少?如果A是降序呢?
解：
升序：O(nlgn)
降序：O(nlgn)
第七章 快速排序
伪代码和维护的性质
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)PARTITION(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x
i = i+1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1
性能分析
最坏情况性能分析
最坏情况发生在每次划分的子问题包含n-1个元素和个元素的时候。
可以写出递归式：T(n)=T(n-1)+T(0)+\Theta (n)=T(n-1)+\Theta (n)。
求解递归式得到时间复杂度为\Theta (n^2)。
平衡情况的性能分析
假设划分为9:1，得到递归式：T(n)=T(9n/10)+T(n/10)+cn，求解递归式得到时间复杂度为O(nlgn)。
随机化
RANDOMRIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)RANDOMRIZED-QUICKSORT(A, p, r)
if p < r
q = RANDOMRIZED-PARTITION(A, p, r)
RANDOMRIZED-QUICKSORT(A, p, q-1)
RANDOMRIZED-QUICKSORT(A, q+1, r)第八章 线性时间排序
排序算法的下界
定理：在最坏情况下，任何比较排序算法都需要做\Omega (nlgn)次比较。
计数排序
COUNTING-SORT(A, B, k)
let C[0..k] be new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]]+1
for i = 1 to k
C[i] = C[i]+C[i-1]
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1
基数排序
根据数字位数排序，从低位到高位，每次使用稳定的排序算法。
引理8.3：给定n个d位数，其中每一个数位有k个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时\Theta (n＋k)，那么它就可以在\Theta (d(n＋k))时间内将这些数排好序。
桶排序
将数组元素所在的区间划为几个桶，将数字装桶后，对每个桶使用插入排序（或者其他稳定的排序算法），期望时间复杂度为\Theta (n)。
习题
8.1-1
在一棵比较排序算法的决策树中，一个叶结点可能的最小深度是多少?
解：
n-1
8.2-2
证明COUNTING-SORT是稳定的。
解：
证明：对一个数列A进行计数排序，假设数列A中存在若干个由相等的元素组成的子列，将这些子列的下标构成若干个升序排列的下标数列集\{\{a_n\},\{b_n\},...\}。考虑数列\{a_n\}，不妨设其中含有n个元素，下标对应的元素值为a，则对于辅助数列C，构造时，有C_{new}[a] = n，加总计算后，对于数列中每个元素，有C_{new}[a]=\sum_{i = 0}^{a}C_{origin}[i]。按照辅助数列对A进行计数排序，记录每一个元素a在已排序数列B中的下标，得到数列\{\tilde{a}_n\}，\tilde{a}_n = C_{new}[a]-n，因此数列\{\tilde{a}_n\}是一个单调递减数列，与数列\{a_n\}倒序的单调性相同。因此可以认为，元素a在排序后的数组B中的下标依旧保持原本的单调性。考虑下标数列集\{\{a_n\},\{b_n\},...\}的每一个元素，均可以用上述语句证明。
已知数列A中每个元素的下标数列和此元素在B中的下标数列保持相同的单调性，又由于排序得到的数组整体有序，所以计数排序是稳定的。
8.2-3
假设我们在COUNTING-SORT的第10行循环的开始部分，将代码改写为:
for j = 1 to A.length该算法还是正确且稳定的吗？
解：
正确但不稳定。原本在后面的元素会被放到B数组靠前的位置。
8.2-4
设计一个算法，它能够对于任何给定的介于0到h之间的n个整数先进行预处理，然后在O(1)时间内回答输入的n个整数中有多少个落在区间[a..b]内。你设计的算法的预处理时间应为\Theta (n+k)。
解：
前缀和。
8.3-2
下面的排序算法中哪些是稳定的:插入排序、归并排序、堆排序和快速排序?给出一个能使任何排序算法都稳定的方法。你所给出的方法带来的额外时间和空间开销是多少?
解：
插入，归并是稳定的排序算法。
扩充元素，增加一个存储下标的变量。排序时将下标作为第二关键字排序。
额外空间开销\Theta(n)。不改变渐进时间复杂度，但会增加常数因子。
8.4-2
解释为什么桶排序在最坏情况下运行时间是\Theta(n^2)?我们应该如何修改算法，使其在保持平均情况为线性时间代价的同时，最坏情况下时间代价为O(nlgn)?
解：
如果桶划分得不好，所有元素集中在同一个桶内，则变成了对n个元素使用插入排序，最坏时间复杂度为\Theta(n^2)。
对每个桶使用归并排序。
第九章 中位数和顺序统计量
顺序统计量：第i个顺序统计量是数组中第i小的元素。
同时寻找最小值和最大值
事实上，我们只需要最多3[n/2]次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值。但我们并不是将每一个输人元素与当前的最小值和最大值进行比较——这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较。
如何设定已知的最小值和最大值的初始值依赖于n是奇数还是偶数。如果n是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与n是奇数的情形一样，成对地处理余下的元素。
下面来分析一下总的比较次数。如果n是奇数，那么总共进行3[n/2]次比较。如果n是偶数，则是先进行一次初始比较，然后进行3(n一2)/2次比较，共3n/2一2次比较。因此，不管是哪一种情况，总的比较次数至多是3[n/2]。
期望时间为线性的选择算法
RANDOMIZED-SELECT(A, p, r, i)
if p==r
return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q-p+1
if i==k
return A[q]
else if i < k
return RANDOMIZED-SELECT(A, p, q-1, i)
else return RANDOMIZED-SELECT(A, p+1, r, i-k)RANDOMRIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)PARTITION(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x
i = i+1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1最坏情况为线性的选择算法
- 将数组划分为
\lfloor n/5 \rfloor组，每组5个元素，最后一组由n mod 5个元素组成 - 寻找每组的中位数，使用插入排序
- 对第二步找出的
\lceil n/5 \rceil个中位数，递归调用SELECT找到中位数x - 按照x调用PARTITION划分数组，x是第k小的元素
- 如果i=k，返回k。否则则按照i比k大或者小对两侧分区递归调用SELECT找出第i小的元素或第i-k小的元素
习题
9.3-1
在算法SELECT中，输入元素被分为每组5个元素。如果它们被分为每组7个元素，该算法仍然会是线性时间吗?证明:如果分成每组3个元素，SEIECT的运行时间不是线性的。
解：
每组7个元素，算法依旧是线性时间。
接下来证明如果分成每组3个元素，SEIECT的运行时间不是线性的。
如果每组只有3个元素，2(\lceil \frac{1}{2} \lceil \frac{n}{3} \rceil \rceil - 2) \geqslant \frac{n}{3} - 4
T(n) \leqslant cn/3+c+2cn/3+4c+an = cn + 5c + an，
5c + an > 0，所以不是线性时间。
9.3-3
假设所有元素都是互异的，说明在最坏情况下，如何才能使快速排序的运行时间为O(nlgn)。
解：
使用SELECT选择中位数的中位数再调用PARTITION。
第十五章 动态规划
设计动态规划算法的四个步骤
- 刻画最优解特征
- 递归地定义最优解的值
- 自底向上计算最优解的值
- 利用计算出的信息构造最优解
动态规划问题的基础
最优子结构：最优解包含子结构的最优解。
重复子问题：子问题被反复运算多次。
钢条切割问题
dp[i]代表长度为i的钢条经过切割后的最优卖出价格。
a[i]代表长度为i的钢条不经切割能卖出的价格。
dp[i] = max{a[i],dp[i-1]+a[1], dp[i-2]+a[2],...,dp[1]+a[i-1]}。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int a[10005] = {0};
int dp[10005] = {0};
//输入钢条总长度p，价格标注的最大长度为n，然后输入n个数，代表长度为i的钢条的价格
int main(){
int p, n;
cin>>p>>n;
for(int i = 1; i <= n; i++)
scanf("%d", a+i);
dp[1] = a[1];
for(int i = 2; i <= p; i++){
int tmpMax = a[i];
for(int j = 1; j < i; j++){
int tmp = dp[i-j]+a[j];
if(tmp > tmpMax)
tmpMax = tmp;
}
dp[i] = tmpMax;
}
cout<<dp[p]<<endl;
return 0;
}矩阵链乘法
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
/*
********************************************
* 输入一串空格分割的整数代表矩阵链规模数组
* 输出矩阵加括号的方式
********************************************
*/
ull a[1001] = {0};
ull dp[1001][1001] = {{0}};
ull s[1001][1001] = {{0}};
void myPrint(int i, int j){
if(i==j)
cout<<"A"<<i;
else{
cout<<"(";
myPrint(i, s[i][j]);
myPrint(s[i][j]+1, j);
cout<<")";
}
}
int main(){
int cnt = 0;
while(1){
cin>>a[cnt++];
if(cin.get()=='\n')
break;
}
for(int l = 2; l < cnt; l++){
for(int i = 1; i < cnt-l+1; i++){
int j = i+l-1;
dp[i][j] = 1e9;
for(int k = i; k < j; k++){
int tmp = dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
if(tmp < dp[i][j]){
dp[i][j] = tmp;
s[i][j] = k;
}
}
}
}
myPrint(1,cnt-1);
return 0;
}最长公共子序列
#include <bits/stdc++.h>
using namespace std;
int main(){
//存储字符串
vector<char> v1;
vector<char> v2;
char ch;
while((ch=getchar())!='\n')
v1.push_back(ch);
while((ch=getchar())!='\n')
v2.push_back(ch);
//构造三维dp矩阵
char dp[101][101][2];
int v1len = v1.size()+1;
int v2len = v2.size()+1;
int maxlen = 0;
int maxi = 0;
int maxj = 0;
for(int i = 1; i < v1len; i++)
dp[i][0][0] = 0;
for(int i = 0; i < v2len; i++)
dp[0][i][0] = 0;
for(int i = 1; i < v1len; i++){
for(int j = 1; j < v2len; j++){
if(v1[i-1]==v2[j-1]){
dp[i][j][0] = dp[i-1][j-1][0]+1;
dp[i][j][1] = '3';
if(dp[i][j][0] > maxlen){
maxlen = dp[i][j][0];
maxi = i;
maxj = j;
}
}
else{
if(dp[i-1][j][0]>=dp[i][j-1][0]){
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = '1';
}
else{
dp[i][j][0] = dp[i][j-1][0];
dp[i][j][1] = '2';
}
}
}
}
//根据dp矩阵构造最优解
stack<char> ans;
while(dp[maxi][maxj][0]>0){
if(dp[maxi][maxj][1]=='3'){
ans.push(v1[maxi-1]);
maxi--;
maxj--;
}
else{
if(dp[maxi][maxj][1]=='1')
maxi--;
else
maxj--;
}
}
while(!ans.empty()){
cout<<ans.top();
ans.pop();
if(ans.size()>0)
cout<<", ";
}
cout<<endl;
return 0;
}最优二叉搜索树
考虑二叉搜索树的任意子树，它必须包含连续关键字k_i,...,k_j, 1 \leqslant i \leqslant j \leqslant n，其叶子节点必然是d_{i-1},...,d_j。
最优二叉搜索树的子树也是一棵相对于其中关键字的最优二叉搜索树。
习题
15.1-3
我们对钢条切割问题进行一点修改，除了切割下的钢条段具有不同价格p,外，每次切割还要付出固定的成本c。这样，切割方案的收益就等于钢条段的价格之和减去切割的成本。设计一个动态规划算法解决修改后的钢条切割问题。
解：
dp[i] = max{a[i], dp[i-1]+a[1]-c, dp[i-2]+a[2]-c,..,dp[1]+a[i-1]-c}
第十六章 贪心算法
解决最优化问题的一种方法。每一步走做出最好的选择，尝试得出全局最优解。
活动选择问题
每个活动有开始时间和结束时间，选择t个时间不重叠的活动，使得t最大。
活动选择问题的最优子结构
考虑任意非空子问题Sk，令am是Sk中结束时间最早的活动，则am在Sk的某个最大兼容活动子集中。
贪心选择性质
指可以通过每次选择最优的步骤来达到全局最优解。
哈夫曼编码
- 利用优先队列
- 贪心选择两个最小的根节点，合并树
第十九章 斐波那契堆
可合并堆
可合并堆是支持以下五种操作的数据结构，其中每个元素都有一个关键字：
MAKE-HEAP()：创建并返回一个新的不含任何元素的堆。
INSERT(H, x)：将一个已填入关键字的元素x插入堆H。
MINIMUM(H)：返回一个指向H中最小关键字元素的指针。
EXTRACT-MIN(H)：从H中删除最小关键字的元素，并返回一个指向该元素的指针。
UNION(H1, H2)：创建并返回一个包含H1，H2所有元素的新堆，并将两个原来的堆销毁。
斐波那契堆还支持以下两个操作：
DECREASE-KEY(H, x, k)：将堆H中关键字为x的元素赋值为k，假设k小于等于x。
DELETE(H, x)：从堆H中删除关键字为x的元素。
斐波那契堆结构
一个斐波那契堆是一系列具有最小堆序的有根树的集合。每棵树均遵循最小堆的性质。
所有斐波那契堆的根节点用循环双向链表链接，每个根的子节点也是用循环双向链表链接。使用循环双向链表的好处有，第一，可以在O(1)时间内从一个环形双向链表的任何位置插人一个结点或删除一个结点。第二，给定两个这种链表，可以用O(1)时间把它们链接(或把它们“捻接”在一起)成一个环形双向链表。
操作详解
创建一个空的斐波那契堆
H.n = 0
H.min = NIL插入一个结点
FIB-HEAP-INSERT(H, x)
x.degree = 0
x.p = NIL
x.child = NIL
x.mark = FALSE
if H.min == NIL
create a root list for H containing just x
H.min = x
else insert x into root list of H
if x.key < H.min.key
H.min = x
H.n = H.n+1
寻找最小结点
return H.min合并两个斐波那契堆
将根节点并入同一个循环链表即可，调整H中的成员变量。
抽取最小结点
FIB-HEAP-EXTRACT-MIN(H)
z = H.min
if z != NIL
for each child x of z
add x to the root list H
x.p = NIL
remove z from the root list of H
if z==z.right
H.min = NIL
else H.min = z.right
CONSOLIDATE(H)
H.n = H.n-1
return zCONSOLIDATE(H)
let A[0..D(H.n)] be a new array
for i = 0 to D(H.n)
A[i] = NIL
for each node w in the root list of H
x = w
d = x.degree
while A[d] != NIL
y = A[d]
if x.key > y.key
exchange x with y
FIB-HEAP-LINK(H, y, x)
A[d] = NIL
d = d+1
A[d] = x
H.min = NIL
for i = 0 to D(H.n)
if A[i] != NIL
if H.min == NIL
create a root list for H containing just A[i]
H.min = A[i]
else insert A[i] into root list of H
if A[i].key < H.min.key
H.min = A[i]FIB-HEAP-LINK(H, y, x)
remove y from the root list of H
make y a child of x, incrementing x.degree
y.mark = FALSE双层循环，合并相同度数的根节点，直到根链表中每个链表的度数不一样。
D(n) = lgn，算法摊还代价为O(lgn)。
关键字减小和删除结点
将关键字减小后，如果需要切割，则标记它的父结点，将它移到根节点链表中。如果它的父节点已经被标记过，则递归地对父节点进行同样的操作。
删除节点，先将此结点的值减小为-inf，然后抽取这个节点即可。
第二十二章 基础图算法
拓扑排序
调用DFS，每个结点访问后插入链表首端。
时间复杂度\Theta (V+E)。
第二十三章 最小生成树
循环不变式
在每次循环之前，A是最小生成树的一个子集。
如果将边(u, v)加入集合A，并且不破坏上述循环不变式，则称这条边为安全边。
一些定义
切割（简称割）：将集合V划分为S和V-S，这种划分称为图的一个切割(S, V-S)。
横跨切割：如果边(u, v)的一个端点位于S中，另一个端点位于V-S中，则称边横跨切割(S, V-S)。
尊重：如果边的集合A中不存在横跨切割的边，则称该切割尊重集合A。
轻量级边：横跨切割的边中权重最小的（不唯一）。
判别安全边
Kruskal算法
排序所有边，然后从小到大选择边加入集合，加入前要判断这条边的加入不会使得集合中的边形成环路。
Prim算法
维护集合A，每次选择割(A, V-A)的轻量级边加入。
第二十四章 单源最短路径
一些概念
负环：如果存在一条环路，从起点经过循环回到此点经过的总路径长度为负，则称此环路为负环。如果图中存在负环，则不存在最短路径。
环路：字面意思。最短路径不可能包含环路。
松弛操作
对于每个结点v，有v.d记录s到v的最短路径权重上界，称为最短路径估计。
对一条边的松弛过程为：将s->u的最短路径距离加上(u, v)权重，与当前的v.d进行比较，如果前者更小，则更新v.d，更新v的前驱结点。
Bellman-Ford算法
Bellman-Ford算法可以解决一般情况的单源最短路径问题，允许边权为负值。它返回一个bool值，表明是否存在负环。如果存在负环，则没有解。如果不存在，则给出最短路径的权重。
Bellman-Ford算法对每个边进行V-1次松弛操作。
双层循环结束后，再对每一条边尝试进行一次松弛操作，如果还有边能够松弛，说明存在负环。否则每个结点的d值就是s到这个节点的最短路径值。
总运行时间为O(VE)。
Dijkstra算法
要求所有边权非负。
维护一个集合A，每次从集合V-A中选择估计值最小的结点，将从此结点出发的所有边松弛，将结点加入集合A。
总运行时间O((V+E)lgV)。
第二十五章 所有结点对的最短路径
动态规划解
可以使用快速幂来优化运行时间到\Theta (n^3lgn)。
Floyd-Warshall算法
有向图的传递闭包
如果存在一条从v_i到v_j的路径，则在新的图G中，存在边(v_i, v_j)。新的图称为原图的传递闭包。
给原图G的边权赋值为1，运行Floyd-Warshall算法，如果D_{ij} < n则存在路径。
用于稀疏图的Johnson算法
增加额外节点，和所有原图的结点相连，边权为0。通过Bellman-Ford算法计算出额外节点到每个结点的最短路径，记为h[i]。再对原图的每个节点运行dijkstra算法，在计算路径(u, v)时，采用公式d[u,v]=w[u,v]+h[u]-h[v]。然后最后还原到真实的路径d[u,v]=d[u,v]-h[u]+h[v]。
第二十六章 最大流
流网络
流网络G=(V, E)的定义
G=(V,E)是一个有向图。- 图中每条边
(u,v) \in E有一个非负的容量值（cost）c(u,v) \geqslant 0。 - 定义
c(u,v)=0，如果(u,v) \notin E。并且图中不允许有自循环。即，对节点v_i,v_j，如果c(v_i, v_j) \neq 0，那么c(v_j, v_i) = 0。
分辨出两个特殊的节点：
- 源节点
s - 汇点
t
对于每个节点v，存在一条s~v~t的路径。并且有|E| \geqslant |V| - 1。
第二十九章 线性规划
在给定有限的资源和竞争约束情况下，很多问题都可以表述为最大化或最小化某个目标。如果可以把目标描述为某些变量的一个线性函数，而且可以将资源的约束指定为这些变量的等式或不等式，那么我们得到一个线性规划问题(linear-programming problem)。
定义：线性规划是研究在一组线性不等式或线性等式约束下，使得某一先行目标函数取最大（或者最小）的极值问题。
标准型
最大化某个公式，约束条件都是线性不严格不等式。
松驰型
最大化某个公式，约束条件都是线性等式。
转化思路
目标函数要最小化：目标函数系数取负，可以转化为最大化。
变量不具有非负约束：x=x1-x2。
可能有等式约束：用一对不等式替换。
有大于等于号：两边同时乘以-1。
标准型转化为松弛型
引入新变量，代表不等式两边的差值。差值大于等于0。
这个变量称为松弛变量。
基本变量：引入的变量。
非基本变量：题目中原来的变量。
基本解：将非基本变量设为0，计算基本变量得出的一组解。此时目标函数值为0。
单纯形算法
选择一个非基本变量作为入基变量，找它最紧的约束，将它取最大值。然后将这个约束的基本变量改写为非基本变量。改写整个线性规划的约束。反复上述操作直到目标函数中的三个非基本变量系数为负数，全部取0即可得到最大值。