definitely-stic
算法导论复习资料
一、选择题：第一章的概念、术语。
二、考点分析：
1
、复杂度的渐进表示，复杂度分析。
2
、正确性证明。
< br>考点：
1
）正确性分析（冒泡，归并，选择）
；
2
）复杂度分析（渐进表示
O
，Ｑ，
?
，替换法证
明，先猜想，然后给出递归方程）
。
循环不变性的三个性质：
1
）初始化：它在循环的第一轮迭代开始之前，应该是正确的；
2
）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一
次迭代开始之前，它也
应该保持正确；
3
）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。<
/p>
插入排序算法：
INSERTION-SORT(A)
1
for j
←
2 to
length[A]
2
3
4
5
6
7
do key
←
A[j]
?
Insert A[j] into the sorted sequence
A[1
，
j - 1].
i
←
j
- 1
while i > 0 and A[i] >
key
do A[i + 1]
←
A[i]
i
←
i -
1
8
A[i + 1]
←
key
插入排序的正确性证明：课本
11
页。
归并排序算法：课本
17
页及
19
页。
归并排序的正确性分析：课本
20
页。
3
、分治法（基本步骤，复杂度分析）
。——许多问题都可以递归求解
考点：快速
排序，归并排序，渐进排序，例如：
12
球里面有一个坏球，怎
样用最少的次数找出
来。
（解：共有
2
4
种状态，至少称重
3
次可以找出不同
的球）
不是考点：线性时间选择，最接近点对，斯特拉算法求解。
解：基本步骤：
一、分解：将原问题分解成一系列的子问题；
二、解决：递归地解各子问题。若子问题足够小，则直接求解；
三、合并：将子问题的结果合并成原问题的解。
复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，
T(n
)
为一个规模为
n
的运
行时间，得到递归式
T(n)=Q(1)
n<=c
T(n)=aT(n/b)+D(n)+C(n)
n>c
附加习题：请给出一个运行时
间为
Q(nlgn)
的算法，使之能在给定的一个由
n
个整数构成的集合
S
和
另一个整数
x
时，判断出
S
中是否存在有两个其和等于
x
的元素。
4
、动态规划（最优子结构性质，自底向上填表计算最优解值（即最长公共子序
列）
，导出最优
解）
。
考点：最优子结构性质，自底向上填表计算最优解值，导出最优解。
a
）动态规划算法设计的
4
个步骤：
1
）描述最优解的结构
；
2
）递归定义最优解的值；
3
）按自底
向上的方式计算最优解的值；
4
）由计算出的结果构造一个最优解。
b<
/p>
）最优子结构遵循的共同模式：
1
）问题
的一个解可以是做一个选择，做这种选择可能会
得到一个或多
个有待解决的子问题；
2
）
假设对一个
给定的问题，
已知的是一个可以导致最优解
的选择，不必关心如
何确定这个选择，尽管假定它是已知的；
3
）在已知这个选择后
，要确定哪
些子问题会随之发生，
以及如何最好地描述所得到的
子问题的空间；
4
）
利用一种
“
剪切粘贴法
”
，
来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。
备注：
A
problem
exhibits
optimal
substructure
if
an
optimal
solution
to
the
problem
contains
within
it
optimal
solutions to subproblems.
Whenever
a
problem
exhibits
optimal
substucture
it
is
a
good
clue
that
dynamic
programming might apply.
c
）最长公共子序列的算法：这里以
两个序列
X={x1,x2,
…
,xm
}
和
Y={y1,y2,
…
,yn}
为输入，注意课本
211
页的自底向上填表方法。
LCS-
LENGTH(X, Y)
1
m
←
length[X]
2 n
←
length[Y]
3
for
i
←
1
to
m
4
do
c[i, 0]
←
0
<
/p>
注：此程序运行时间为
O
（
mn
）
，每个表项的计算时间为
O
（
1
）
5
for
j
←
0
to
n
6
do
c[0, j]
←
0
7
for
i
←
1
to
m
8
9
10
11
12
13
14
15
16
do for
j
←
1
to
n
do if
xi = yj
then
c[i, j]
←
c[i - 1, j - 1]
+ 1
b[i, j]
←
“=
else if
c[i - 1, j]
≥
c[i, j - 1]
then
c[i, j]
←
c[i -
1, j]
b[i, j]
←
↑
else
c[i, j]
←
c[i, j - 1]
b[i, j]
←
←
17
return
c and b
PRINT-LCS(b, X, i, j)
1
if
i = 0 or j = 0
2
then
return
< br>注：此程序运行时间为
O
（
m+
n
）
3
if
b[i, j] =
4
5
then
PRINT-LCS(b, X, i - 1, j - 1)
print xi
6
elseif
b[i, j]
=
↑
7
8
then
PRINT-LCS(b, X, i - 1, j)
else
PRINT-LCS(b, X, i, j -
1)
d
）矩阵链乘法的算法：参照
课本上的矩阵链表得出矩阵相乘的最小算法。
m
[
i
,
j
< br>]
?
m
in
{
m
[
i
,
k
]
?
m<
/p>
[
k
?
1
,
j
]
i
?
k
?
j
?
p
i
?
1
p
k
p
j
}
MATRIX-CHAIN-ORDER(p)
每个表项的复杂度是
O
（
n
）
，共有
O
（
n^2
）表项，则为
O
（
n^3
）
1
n
←
length[p] - 1
2
for
i
←
1
to
n
3
do
m[i, i]
←
0
4
for
l
←
2
to
n
?
l is the chain length.
5
6
7
8
9
10
11
12
do for
i
←
1
to
n - l + 1
do
j
←
i + l - 1
m[i, j]
←
∞
for
k
←
i
to
j - 1
do
q
←
m[i, k] + m[k + 1, j] + pi-1 pkpj
if
q
< m[i, j]
then
m[i, j]
←
q
s[i, j]
←
k
13
return
m and s
PRINT-OPTIMAL-PARENS(s, i,
j)
1
if
i = j
2
3
4
5
then
print
else
print
PRINT-OPTIMAL-
PARENS(s, i, s[i, j])
PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)
6 print
e
）备忘录算法：
1
）程序结
构采用自顶向上；
2
）保留了递归结构，开销较大；
3
）当所有的子
问题都需要求解时，自底向上的方
法效率较高，否则可以采用备忘录方法。
备忘录算法的代码可
以参照课本
207
页。
f
）最优二叉查找树：
1
）
一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是
把有最大概率的关键
字放在根部来构造一棵最优二叉查找树。
5
< br>、贪心法（最优子结构性质
+
贪心选择性质）
。
考点：学会证明最优子结构性质和贪心选择性质的问题。
a
）活动选择问题：
注意课
本上
224
页地贪婪法定理证明，这就是贪婪法的合理性证明。
RECURSIVE-ACTIVITY-
SELECTOR(s, f, i, j)
1 m
←
i + 1
2
while
m < j and sm < fi
?
Find the first
activity in Sij.
3
do
m
←
m + 1
4
if
m < j
5
then return
{am}
∪
RECURSIVE-
ACTIVITY-SELECTOR(s, f, m, j)
6
else return
GREEDY-ACTIVITY-SELECTOR(s,
f)
?
0
if
S
ij
?
?
?
c
[
i
,
j
]
?
?
{
c
[
i
,
< br>k
]
?
c
[
k
,
j
]
?
1
}
if
S
ij
?
?
max
?
?
i
?
k
?
j
1 n
←
length[s]
2 A
←
{a1}
3 i
←
1 2
4
for
m
←
2 to n
5
6
7
do
if
sm
≥
fi
then
A
←
A
∪
{am}
i
←
m
8
return
A
b
）贪心算法遵循的步骤：
1
）决定问题的最优子结构；
2
）设计出一个递归解；
3
）证明在递归
的任一阶段，最优选择之一总是贪
心选择，那么，做贪心选择总是安全的；
4
）证明通过做贪心<
/p>
选择，所有的子问题（出一个以外）都为空；
5
< br>）设计出一个实现贪心策略的递归算法；
6
）将
递归算法转换成迭代算法。
c
）根据贪心选择来构造最优子结构：
1
）将优化问题转
化成这样一个问题，即先做出选择，再
解决剩下的一个子问题；
2
）
证明原问题总是有一个最优解是做贪心选择得到的，
从而说明贪心
选择的安全；
3
）说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的
最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。
d
）贪心选择性质：证明定理
e
）最优子结构性质：课本
229
页。
6
、搜索（回溯法
、剪枝函数、最小成本优先）
。
考点
：回溯，剪枝函数，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。
a
）回溯法：
1
）定义：回溯法
< br>(
探索与回溯法
)
是一种选优搜
索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或
达不到目标，就退回一步重新选择，这种走不通
就退回再走的技术为回溯法，而满足回溯
条件的某个状态的点称为
“
回溯点
”<
/p>
。
2
）回溯法解题的步骤：
a
、针对所给的问题，定义问题的解空间；
b
、确定易于搜索的解空间结构；
<
/p>
c
、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免
无效搜索。
2
）回溯法解决的
n
后问题：在一个
n * n
的棋盘上放置
n
个王后，使得
n
后彼此不受攻击。
3
）回溯法解决
0-1
背包问题：
附：证明部分背包问题具有贪心选择性质。
课本练习题：
c
剪枝函数：约束函数：剪去不满足约束函数的子树；