大家好，欢迎来到IT知识分享网。

我们学校开设的这门课，过于理论，实践太少，考试不会太难，一起学习，一起 不挂科！
但是算法平时一定要练哦！加油！
内容摘自老师PPT及复习资料，感谢！

感兴趣的话可以参考 算法竞赛、小白学DP(动态规划) 学习相关代码的具体实现(Java版)

课程介绍

算法分析基础

算法的定义

算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列。

算法正确性

对每一个输入实例算法都能终止，并给出正确输出。

算法的性质

(1)输入：有外部提供的量作为算法的输入。
(2)输出：算法产生至少一个量作为输出。
(3)确定性：组成算法的每条指令是清晰，无歧义的。
(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（可行性）

程序的定义

程序是算法用某种程序设计语言的具体实现。

程序与算法的区别

程序可以不满足算法的性质(4)（有限性）。
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，当子程序得到输出结果后便终止。

这个好像要考(*￣︶￣)

算法设计和分析的步骤

（1）问题的陈述。
（2）模型的选择。
（3）算法的设计。
（4）算法的程序实现。
（5）算法分析。

复杂度分析

算法复杂性 = 算法所需要的计算机资源
1、考虑算法的好坏主要有以下几点：
（1）执行算法所耗费的时间。
（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
（3）算法应易于理解，易于编码，易于调试等。

2、影响程序运行时间的主要因素 ：
（1）程序的输入。
（2）由编译系统所产生的代码程序的质量。
（3）执行程序的计算机机器指令的性能与速度。
（4）程序所依据的算法的时间复杂度。

3、算法的复杂性测度主要有两个方面：
(1) 时间复杂度 T(n)
(2) 空间复杂度 S(n)
其中n是问题的规模（输入大小）。

算法的复杂性取决于：

(1)求解问题的规模N；
(2)具体的输入数据I；
(3)算法本身的设计

可操作性最好且最有实际价值的是最坏情况下的时间复杂性。

算法的时间复杂性

算法渐近复杂性

渐近分析的记号

渐近上界记号

渐近下界记号

非紧上界记号

非紧下界记号

紧渐近界记号

意义

算法分析中常见的复杂性函数

算法分析方法

算法分析的基本法则

递归

基本概念

递归的概念:

直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。

说明:

1、递归程序必须有终止条件。否则就总是自我调用，永不终止。
2、尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的。
3、用递归过程来描述它们不仅非常自然，而且证明该算法的正确性要比相应的非递归形式容易得多。
4、递归过程的优点：结构清晰，程序易读，正确性容易证明 。
5、缺点：运行的效率比较低 、花时间。
6、实现递归过程的关键在于为过程的递归调用建立一个先进后出型调用堆栈 。一个过程要有一个相应的递归调用堆栈。

欧几里得算法：已知两个非负整数m，n，且m>n>0，求这两个数的最大公因子。

欧几里得得出本算法基于这样一种观察，两个整数m和n的最大公因子等于n与m mod n的公因子。欧几里得算法如下：

GCD (m，n)
1       if n=0
2           then return m
3       return  GCD (n，m  mod n) 

递归优缺点

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

递归树方法

基于递归树的方法可以更好地猜测一个问题的解，并用替换方法证明这个猜测。

递归树的生成规则：

1. 初始，递归树只有根结点，其值为W(m)；
2. 不断继续下述过程：
   将函数项叶结点的迭代式W(mi)表示成二层子树；
   用该子树替换该叶结点；
3. 继续递归树的生成，直到树中无函数项(只有初值)为止。

例题：解递归方程T(n)=3T(n/4)+cn2。假设n为4的幂。

递归树的构造过程如下：

分析：

图(a)表示T(n)。
图(b)表示对T(n)进行扩展，形成与递归方程等价的一棵树。cn2表示树的根，即递归顶层的开销。根的三棵子树为小一级的递归方程T(n/4)。
图( c )表示对T(n/4)的进一步展开。根据递归方程，继续展开树中的每个结点，直到问题规模变成1，每个开销为T(1)。
图(d)表示最终结果树。树的高度是log4n，深度为log4n+1。

例题： T(n)=2T(n/2)+n-1

T(n)=kn-(2k-1)=nlogn-n+1=O(nlogn)

主方法

主方法(master method)为我们提供了解如下形式递归方程的一般方法。
T(n)=aT(n/b)+f(n)

• 其中a≥1，b>1为常数，f(n)是渐近正函数。
• 递归方程 T(n)=aT(n/b)+f(n) 描述了算法的运行时间，算法将规模为n的问题划分成a个子问题，每个子问题的大小为n/b，其中a、b是正常数。求解这a个子问题，每个所需时间为T(n/b)。函数f(n)表示划分子问题与组合子问题解的开销。
• 每个子问题n/b未必为整数，但用T(n/b)代替T(⌈n∕b⌉)和T(⌊n∕b⌋ )并不影响递归方程的渐近行为，因此我们在表达这种形式的分治算法时将略去向下取整函数和向上取整函数。

主定理

主定理解析

主定理举例

分治法

总体思想

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治法的设计思想是，将一个难以直接解决的大问题，
分割成一些规模较小的相同问题，以便各个击破，
分而治之。
凡治众如治寡，分数是也。
—-孙子兵法

适用条件

分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
• 利用该问题分解出的子问题的解可以合并为该问题的解；
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
• 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

归并排序

归并排序(merge sorting) 是分治法应用的一个实例，由以下三步组成：

(1)划分：将待排序n个元素的序列划分成两个规模为n/2的子序列。
(2)解决：用归并排序递归地对每一子序列排序。
(3)合并：归并两个有序序列，得到排序结果。
当划分的子序列规模为1时，递归结束。因为一个元素的序列被认为是有序的。

算法的复杂度分析

归并算法的改进

• MERGE-SORT算法将待排序集合一分为二，不停递归，直至排序集合只剩1个元素为止。然后不断合并2个排好序的数组段。
• 递归算法运行效率低，怎样从分治策略的机制入手，消除算法中的递归？
• 方案：首先将数组中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，如此继续，直至整个数组排好序。

快速排序

快速排序由C. A. R. Hoare在1960年提出。

基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

动态规划

算法总体思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态规划基本步骤

1）找出最优解的性质，并刻划其结构特征。
2）递归地定义最优值。
3）以自底向上的方式计算出最优值。
4）根据计算最优值时得到的信息，构造最优解。

动态规划算法的基本要素

最优子结构

• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）。

重叠子问题

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
  

备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同(自顶向下)，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

0-1背包实例

最长公共子序列

矩阵连乘

分析最优解的结构

建立递归关系

递归的复杂性

计算最优值

DP求解的复杂度分析

构造最优解

贪心算法

贪心算法与分治法和动态规划算法的关系

1）分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。
2）动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。
3）贪心法与动态规划法和分治法类似，都是将问题分解为规模更小的、相似的子问题，并通过求解子问题产生一个最优解。
有些具有最优子结构性质的问题，可以用动态规划算法求解，但是用贪心算法更简单、更直接，且解题效率更高。

贪心算法的基本思想

贪心法的当前选择可能要依赖已经做出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地做出贪心选择。

贪心法总是做出在当前时刻看起来最优的决策，即希望通过局部最优决策导致问题的全局最优解。

特别说明：贪心法并不总是产生问题的全局最优解，但许多问题利用贪心法求解得到全局最优解。

贪心算法的基本要素

贪心选择(greedy-choice)的性质

• 利用贪心算法的第一步，是问题具有贪心选择的性质，通过局部最优选择(贪心)，可以得到问题的全局最优解。
• 当考虑要做出哪一个选择时，我们会选择当前看起来最优的，而不考虑子问题的结果。这就是贪心算法和动态规划算法的不同之处。
• 在动态规划算法中，当我们在每一步做出选择时，这个选择通常会依赖于子问题的解。 因而，我们一般会按照自底向上的方式，求解的过程从较小的问题到较大的问题，最后解决原问题。
• 而在贪心算法中，我们首先会做出当前看起来最优的选择，然后解决选择之后出现的子问题。 贪心算法的选择可能取决于到目前为止所做的选择， 但不会依赖于未来的选择，也不会依赖于子问题的解。因此，采用贪心策略解问题的过程通常按照自顶向下的方式逐次进行贪心选择，将每一给定问题实例减少到更小问题实例。

最优子结构(optimal substructure)

• 如果问题的最优解中包含子问题的最优解，则问题展示了最优子结构。这个性质是评价应用动态规划以及贪心算法的基本性质。背包问题和活动选择问题都具有最优子结构性质。
• 在背包问题中，如果问题的一个最优解包含物品j，我们从最优装包中去掉物品j的一个权值w，那么，余下至多为W-w的容量，一定包括n-1个物品以及物品j的权值为wj-w的最优装包方式。

两个背包问题

背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品的全部。

• 尽管这两个问题很相似，但是背包问题可用贪心法求解， 而0-1背包问题却不能。
• 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
• 事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上动态规划算法的确可以有效地解0-1背包问题。

前缀码

二元前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀。

回溯算法

使用回溯法的问题特征：当需要找出问题的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

搜索策略：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

子集树的构造
0-1背包问题对应的解空间就是一棵子集树, 树中所有结点都可能成为问题的一个解。子集树中至多有2n个叶结点。
因此，任何算法遍历子集树所需运行时间为Ω(2n)。

排列树的构造

搜索树的构造

生成问题状态的方法

回溯法的基本思想

(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。

n皇后问题

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

4皇后问题：棋盘上的行和列从1到4编号，同时也给皇后从1到4编号。由于每一个皇后应放在不同的行上，假设皇后i放在第i行上，因此4皇后问题可以表示成4元组(x1, x2, x3, x4)， 其中xi(i=1, 2, 3, 4)表示皇后i所放置的列号。

显式约束条件是Si={1, 2, 3, 4}，i=1, 2, 3, 4。在这种情况下，解空间为4^4个4元组组成。

隐式约束条件是没有两个xi相同(即所有皇后必须在不同列上)，且满足不存在两个皇后在同一条对角线上。加上隐式约束条件，问题的解空间可进一步减小。此时，解空间大小为4!，因为所有解都是4元组的一个置换。

4皇后问题的解空间

可以用一棵树表示4皇后问题的解空间。 由于4皇后问题的解空间为4!种排列，因此将要构造的这棵树是一棵排列树。

使用剪枝函数的4皇后问题的状态空间树

• 在实际中，并不需要生成问题的整个状态空间，可以通过使用剪枝函数来杀死那些还没有生成其所有子结点的活结点。
• 下图是使用剪枝函数的4皇后问题的部分状态空间树，图中一个结点一旦被剪枝函数杀死，则用B做上记号。

• 在4皇后问题中，惟一开始结点为根结点1，路径为()。开始结点既是一个活结点，又是一个扩展结点, 它按照深度优先的方式生成一个新结点2，此时路径为(1)，这个新结点2变成一个活结点和新的扩展结点，原来的扩展结点1仍然是一个活结点。
• 结点2生成结点3，但立即被杀死。于是，回溯到结点2，生成它的下一个结点8，且路径变为(1, 3)。
• 结点8成为扩展结点，由于它的所有子结点不可能导致答案结点，因此结点8也被杀死。回溯到结点2，生成它的下一个结点13，且路径变为(1, 4)。

n皇后问题及回溯算法

将4皇后问题推广到n皇后问题(n-queen problem)，即找出n×n的棋盘上放置n个皇后并使其不能互相攻击的所有解。

设X =(x1, x2, …, xn)表示问题的解，其中xi表示第i个皇后放在第i行所在的列数。

• 解向量：(x1, x2, …, xn)
• 显约束：xi=1,2, … ,n
• 隐约束：
  1)不同列：xixj
  2)不处于同一正、反对角线：|i-j||xi-xj|

N-QUEEN算法代码分析

• 第1~2行进行初始化。
• 第3行的while 循环表示，对于所有行执行循环体，计算xk值。
• 在第5~6行的while循环中，对于每一个xk值，调用PLACE过程测试它的合法性, 即寻找满足约束条件的xk值。
• 第7行中，如果找到一个放置位置，则进一步测试，所求(x1, x2, …, xk)是否为问题的解，这只需判断k是否等于n。如果是问题的解，则输出(第9行), 否则通过赋值语句将k值增加1, 继续外层while 循环。
• 如果第7行的条件为假，则表明不存在合法的xk值，此时将k值减1(第12行)，进行回溯。

分支限界法

分支限界法与回溯法的区别

（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法基本思想

• 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
• 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
• 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法

(1) 先进先出(first in first out，简称FIFO)分支限界法(FIFOBB)。在先进先出的分支限界法中，用队列作为组织活结点表的数据结构，并按照队列先进先出的原则选择结点作为扩展结点。
(2) 优先队列(priority queue，简称PQ)分支限界法(PQBB)。 在优先队列分支限界法中，用优先队列作为组织活结点表的数据结构，每个结点都有一个成本或价值，按照最大价值(greatest value)/最小成本(least cost)的原则选择结点作为扩展结点。

两种分支限界法的异同

先进先出状态空间树

优先队列状态空间树

当用优先队列作为组织活结点表的数据结构，并按照结点估值函数值的大小选择下一个扩展结点时，就得到0-1背包问题优先队列状态空间树。

组合优化问题

• 目标函数（极大化或极小化）
• 约束条件：解满足的条件
• 可行解：搜索空间满足约束条件的解
• 最优解：使得目标函数达到极大（或极小）的可行解
• 典型的组合优化问题有：
  旅行商问题（TSP）、生产调度问题、0-1背包问题、装载问题、图着色问题、最大团问题等。

代价函数

• 计算位置：搜索树的结点
• 值：极大化问题是以该点为根的子树所有可行解的值的上界（极小化问题为下界）
• 性质：对极大化问题父结点代价不小于子结点的代价（极小化问题相反）

界

• 含义：当前得到可行解的目标函数的最大值（极小化问题相反）
• 初值：极大化问题初值为0（极小化问题为最大值）
• 更新：得到更好的可行解时

分支限界

停止分支回溯父结点的依据：

1. 不满足约束条件
2. 对于极大化问题，代价函数值小于当前界（对于极小化问题是大于界）。

界的更新：
对极大化问题，如果一个新的可行解的优化函数值大于（极小化问题为小于）当前的界，则把界更新为该可行解的值。

Sample Test

select question

1. 当输入规模为 n 时，算法增长率最小的是 B，最大的是 C。
   
2. 
3. 渐进算法分析是指 当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析
4. 递归通常用 栈 来实现。
5. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 问题规模不同，问题性质相同
6. 对于 0-1 背包问题和背包问题的解法 0-1 背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包 问题则可以用贪心算法求解
7. 具有最优子结构的算法有 动态规划法、贪心算法、分治算法
8. 关于回溯搜索法的介绍：

1）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解。
2）回溯法是一种既带系统性又带有跳跃性的搜索算法。
3）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯。

9. 关于回溯算法和分支限界法

1）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入 活结点表中。
2）回溯法和分支限界法都是在解空间树上搜索问题解的方法。
3）回溯法和分支限界法都可以用来解决组合优化问题。

10. 优先队列通常用以下堆数据结构来实现。
11. 算法分析中，记号 O 表示 渐进上界。
12. 备忘录算法是动态规划算法的变形。
13. 回溯法 不具有最优子结构的算法

分治算法 动态规划算法 贪心算法 有最优子结构

14. 剪枝函数是回溯法中避免无效搜索采取的策略。
15. 用贪心法求解背包问题时的贪心选择策略是 单位容量带来的价值之比
16. 数学归纳法不是求解递归方程的方法。

替换法、 递归树方法、主方法是求解递归方程

17. 算法的性质包括输入、输出、确定性、有穷性、可行性。
18. 一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有有穷特性。
19. 最长公共子序列算法利用的算法是 动态规划算法。
20. 贪心算法的基本要素的是 贪心选择的性质。
21. 若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最坏情况下的时间复杂度为 O(n^2)
22. 回溯法的效率不依赖于下列哪些因素 确定解空间的时间

效率依赖于：满足显约束的值的个数、计算约束函数的时间、计算限界函数的时间。

23. 贪心算法与动态规划算法的主要区别是 贪心性质的选择

最优子结构、构造最优解、定义最优解。

24. 算法的实现依赖于数据结构的设计
25. 分支限界法 通常以广度优先方式系统搜索问题解。
26. 分治算法一定 由三个步骤组成：划分子问题、求解子问题、合并子问题的解。
27. 利用贪心法求解 0/1 背包问题时没有任何准则能够确保最优解。
28. 用递归算法求解 F(5) 时，需要7次加运算，该方法采用的是分治策略。
29. 若一个问题既可以用迭代方式也可以用递归方式求解，则迭代方法具有更高的时空效率。
30. 迪杰斯特拉 (Dijkstra) 算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了贪心算法策略。
31. 在下列算法中得到的解未必正确的是 拉斯维加斯算法
32. 对给定 n 元数组进行排序，应用比较方法进行排序，其时间复杂度下界是 O(n*log2^n)。
33. 回溯法和分支限界算法求解问题时，需要构造对该问题的解空间结构，期排列通常有个 n! 叶节点。
34. 用随机投点发发计算圆周率，在单位矩形上随机投了 n 次，有 k 次落在单位圆内（圆心在单位矩形的一个顶点上），则圆周率为： k/n=PI/4.
35. 有回溯算法求解活动安排问题，其解空间可以用排列树来表示
36. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是 分支界限算法。
37. 子集树的构造

当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树(subset tree)。
有2^n个子集。

排列数的构造

为了构造出所有n!种排列，可以设一个具有n个元素的数组。第k个位置的候选解的集合就是那些不在前k-1个元素的部分解中出现的元素集合。

38. 用分治算法优化大整数相乘，算法复杂度可以达到 O(n^log3)。

O(n^2)

39. 3n2 +10n 的渐进表达式 n^2，10 ^ log3 n的渐进表达式是 n.
40. 在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。
41. 应用Johnson法则的流水作业调度采用的算法是 动态规划算法
42. 汉诺塔问题

1~N从A移动到B，C作为辅助
等价于：
1，1~N-1从A移动到C，B为辅助
2，把N从A移动到B
3，1~N-1从C移动到B，A为辅助

void hanoi(int n, int A, int B, int C){ 
   
	if (n > 0) { 
   
		hanoi(n-1,A,C,B);
		move(n,A,B);
		hanoi(n-1,C,B,A);
	}
}

43. 动态规划的基本要素为 最优子结构与重叠子问题性质
44. 算法分析中，O表示渐进上届，欧美大表示渐进下界，O心中有-表示：紧渐进界，o：非紧上界，w：非紧下界。
    
45. 贪心求解最优解问题，一般重要性质：最优子结构性质与贪心性质的选择。
46. 回溯法的效率不依赖于 问题的解空间形式

依赖于：产生x[k]的时间，产生显约束的x[k]值的个数，计算上界函数约束的所有x[k]的个数，计算约束函数的时间

47. O(g(n))：f(n)存在正常数 c和n0，使得对所有的 n>=n0有：0<=f(n)<=cg(n);（渐进上界）
48. 下列不是动态规划算法基本步骤的是：找出最优解的性质

构造最优解、算出最优解、定义最优解

49. 最大效益优先是（分支界限法）的一搜索方式。
50. 动态规划法 通常以自底向上的方式求解最优解。
51. 衡量一个算法好坏的标准是 时间复杂度低
52. 实现循环赛日程表利用的算法是 分治策略
53. 棋盘覆盖问题、选择问题、归并排序使用分治法求解

0/1背包问题不是。

54. 回溯法 通常以深度优先方式系统搜索问题解。
55. 备忘录方法是那种算法的变形 动态规划法。
56. 哈弗曼编码的贪心算法所需的计算时间为 O(nlogn)。
57. 贪心选择性质 是贪心算法的基本要素。
58. 剪枝函数 是回溯法中为避免无效搜索采取的策略。
59. P类问题包含在NP类问题中。
60. 最优子结构性质是贪心算法与动态规划算法的共同点。
61. Strassen算法采用分治法解决矩阵乘积问题，并通过排列组合的技巧使得分治法产生的递归树不那么“茂盛”以减少矩阵乘法的次数。
62. 使用分治法求解不需要满足的条件是 子问题必须是一样的

子问题不能够重复、子问题的解可以合并、原问题和子问题使用相同的方法解。

63. N皇后问题不能使用贪心法解决（用回溯算法解决）

单源最短路径问题、最小花费生成树问题、背包问题。

64. 贪心算法不能解决0/1背包问题

动态规划、回溯法、分支限界法

65. 动态规划算法基本要素的是 重叠子问题

动态规划算法以自底向下的方式求解最优解

66. 背包问题的贪心算法所需的计算时间为 O(nlogn)
67. 实现大整数的乘法是利用的分治策略算法
68. 0-1背包问题的回溯算法所需的计算时间为o(n*2n)
69. 拉斯维加斯算法找到的解一定是 正确解
70. 实现最大子段和利用的算法是 动态规划法
71. 优先队列式分支限界法选取扩展结点的原则是 结点的优先级
72. 背包问题的贪心算法所需的计算时间为 O(nlogn)
73. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 最优子结构性质

fill blank

1. . 一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间复杂性 和 空间复杂性之分。
2. 算法具有以下五大特性是 确定性 有穷性 可行性 输入 输出
3. 一个直接或间接调用自身的算法称为 递归算法。 出自于“平衡子问题”的思想， 通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同。
4. 使用分治法的三个步骤是 划分 解决 合并
5. 贪心算法的基本要素是 贪心选择的性质 最优子结构
6. 动态规划算法有一个变形方法 备忘录。这种方法不同于动态规划算法“自底 向上”的填充方向，而是“自顶向下”的递归方向，将每个解过的子问题存储下来以 备需要时查看，同样也可避免相同子问题的重复求解。
7. 循环不变式具有以下三个性质 初始、维持、终止
8. 二分查找算法的实现前提是 列表已排好序
9. 动态规划算法的基本要素是 最优子结构性质、子问题重叠性质
10. 若序列 X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列 X 和 Y 的一个最长公共子序列 {BABCD}或{CABCD}或{CADCD}
11. 贪心法总是做出在当前时刻看起来最优的决策，即希望通过 局部最优决策导致问题的 全局最优解。
12. 最优子结构性质的意义是： 问题的最优解包含着其子问题的最优解
13. 回溯法定义问题的状态空间结构包括 子集树、排列树、搜索树
14. 前缀码是指 只用 0/1 对字符进行编码，并限定任一字符的编码都不是另一个字符编码的前缀。
15. 利用主方法可解递归方程的一般形式T(n)=aT(n/b)+f(n)
16. 回溯法与分支限界法搜索方式不同，回溯法按深度优先搜索解空间，分支限界法按广度优先或最小耗费优先搜索解空间。
17. 回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构，其解空间结构通常有 3 种形式，分别是子集树、排列树 、满 m 叉树。
18. 复杂度大小关系：
    
19. 背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分， 而不一定要选择物品的全部。
20. 贪心选择性质是指：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
21. 所谓最优子结构性质是指：问题的最优解包含子问题的最优解。
22. 回溯法：具有限界函数的深度优先生成法。
23. 用回溯算法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前结点扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径长度为 h(n)，则回溯算法所需的空间通常为 O(h(n))。
24. 回溯算法的框架按照问题的解空间一般分为子集树算法框架和排列树算法框架。
25. 用回溯算法求解批处理作业调度问题时，该问题的解空间结构是排列树结构。
26. 描述算法常用方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。
27. 算法设计的要求：正确性和可读性。
28. 算法由操作、控制结构、数据结构三要素组成。
29. 所有递归函数都能找到对应的非递归的定义。
30. 归并排序、二分搜索是分治算法的思想。
31. 动态规划中存储子问题是为了 避免重复求解子问题。
32. 最优子结构是问题能用动态规划求解的前提（也是其基本要素）。
33. 矩阵连乘可由动态规划求解。
34. 最优子结构的性质：原问题的最优解包含其子问题的最优解。（分解出的子问题不相互独立）。
35. 贪心算法不一定满足最优子结构的性质。
36. 回溯算法中限界函数的目的是减去得不到最优解的子树。
37. 活结点表的组织方式不同，分支界限法包括 队列式分支界限算法和优先队列式分支界限算法。
38. 分支界限按 广度优先搜索或最小耗费优先 搜索解空间。
39. 回溯算法与分支界限算法求解问题时，需要构造对该问题的解空间结构，子集树、排列树、满m叉树。
40. 活动安排：

最早开始时间：可以增大资源的利用率。
最早结束时间（更合理）：可以使下一个活动尽早开始。

41. 程序是 算法 用某种程序设计语言的具体实现。
42. 算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
43. 算法是指解决问题的 一种方法 或 一个过程。
44. 从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法。
45. 问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
46. 以深度优先方式系统搜索问题解的算法称为 回溯法。
47. 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划，需要排序的是 回溯法 ，分支限界法。
48. 使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题。
49. 贪心算法的基本要素是 贪心选择性质和 最优子结构性质。
50. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题的解得到原问题的解。
51. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性、有限性四条性质。
52. 大整数乘积算法是用 分治法 来设计的。
53. 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。
54. 快速排序算法是基于 分治策略 的一种排序算法。
55. 动态规划算法的两个基本要素是 最优子结构性质 和 重叠子问题 性质 。
56. 回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
57. 分支限界法主要有 队列式（FIFO） 分支限界法 和 优先队列式 分支限界法。
58. 回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数。
59. 任何可用计算机求解的问题所需的时间都与其 规模 有关。
60. 某一问题可用动态规划算法求解的显著特征是具有 最优子结构性质
61. 用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含 一个最优解。
62. 0-1背包问题的回溯算法所需的计算时间为,用动态规划算法O(n*2n)，所需的计算时间为 O(min{nc,2n})。
63. 输入规模三种度量是 输入元素的个数，二进制表示的总个数 和 对于图可用图中顶点和边数。
64. 本书介绍三种求解递归方程的方法是 替换、递归树和主方法。
65. 动态规划的4个步骤是

①刻画最优解结构、②递归定义最优解的值、③计算最优解的值、④根据计算结果，构造最优解。

66. 算法是将转入转换成输出的计算步骤所组成的序列或描述输入输出关系的特定计算过程。
67. 渐进表示：是方便地表示算法的最坏情况下，计算的复杂度。
68. 运行时间：是指在某个输入时，算法执行操作的次数或者步数。
69. 动态：是所作的决策可能依赖当前状态，而此前所作的决策无关。
70. 算法设计和分析的步骤可概括为：

①问题的陈述。
②模型的选择。
③算法的设计。
④算法的程序实现。
⑤算法分析。

71. 循环不变式的三个性质： ① 初始、② 维持、③ 终止
72. 替换方法的两个步骤是 ①首先猜测问题的解的某个界限间、②然后用数字归纳法证明所测解的正确性
73. 分治方法的三个步骤是： ①划分、②解决、③合并
74. 算法分析：是指对一个算法所需要的计算机资源进行预测。
75. 算法正确性：对每一个输入实例算法都能终止，并给出正确输出。
76. 递归：对自己的调用。
77. 规划：意味着一系列的决策。
78. 运行时间：是指在某个输入时，算法执行操作的次数或者步数。
79. 最坏情况：是指算法的运行时间是任一输入运行时间的上界。
80. 哈夫曼编码：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。
81. 算法 将输入转化为输出的计算步骤所组成的序列或是描述输入输出关系的特定计算过程。
82. 平凡矩阵链乘：在矩阵链乘中不能进行分割矩阵链乘。
83. 快速排序算法的性能取决于划分的对称性。
84. 舍伍德算法是（概率算法）的一种。
85. 背包问题、哈夫曼编码的贪心算法所需的计算时间为 O(n*logn)，0-1背包问题的回溯算法所需的计算时间为 O(n * 2n)。
86. 实现最大子段和利用的算法是 动态规划法。
87. 下列是动态规划算法基本要素的是 重叠子问题。
88. Strassen矩阵乘法是利用（分治策略）实现的算法。
89. 回溯法解旅行售货员问题时的解空间树是 子集树。
90. 在下列算法中有时找不到问题解的是 拉斯维加斯算法。
91. 找出最优解的性质不是动态规划算法基本步骤。

构造最优解、算出最优解、定义最优解

short question

什么是算法？算法的特征有哪些？

算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法就是解决问题的方法或过程。
特征：
1.输入：有零个或多个外部量作为算法的输入。
2.输出：算法产生至少一个量或作为输出
3.确定性：组成算法的每条指令是清晰的，无歧义的
4.有限性 :算法中每条指令的执行次数有限，执行每条指令的时间也有限
5.可行性

考虑算法的好坏主要有以下几点：

1、执行算法所耗费的时间。
2、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
3、算法应易于理解，易于编码，易于调试等。

主定理

1. 简述递归方程 T(n)=4T(n/2)+n 是否可以使用主方法来进行求解。如果可以，写出满足主 定理的哪一种情形，并求解该递归方程；如果不满足，写出理由。

简述分治法的适用条件（特征）

(1)该问题的规模缩小到一定的程度就可以容易地解决；
(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
(3)利用该问题分解出的子问题的解可以合并为该问题的解； (4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

设计动态规划算法的基本步骤

(1) 刻画问题最优解的结构
(2) 递归定义最优解的值
(3) 自底向上的计算问题最优解的值
(4) 根据计算的结果，构造问题最优解

动态规划算法的基本思想

简述分支限界法与回溯法的不同

(1) 求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在 某种意义下的最优解。
(2) 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

简述递归的定义及优缺点

定义：一个直接或间接调用自身的算法。
优点：结构清晰，程序易读，正确性容易证明。
缺点：运行的效率比较低、花时间。

简述回溯法的一般执行步骤

针对所给问题，定义问题的解空间；
确定易于搜索的解空间结构；
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法的基本原理

子集树：O(2n) 2n个叶子结点 2n+1-1个结点。
排列树：O（n!）n!个叶子结点。

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间的任意一个节点时，先判断该节点是否包含问题的解。如果肯定不包含，跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

简述分治法和动态规划算法的相同点和不同点

相同点：二者要求原问题具有最优子结构，都是将问题分而治之分解成若干个规模较 小的子问题；
不同点：分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。而动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。

简述常见的两种分支限界法

(1) 先进先出(first in first out，简称 FIFO)分枝限界法。在先进先出的分枝限界法中， 用队列作为组织活结点表的数据结构，并按照队列先进先出的原则选择结点作为扩展结点。
(2) 优先队列(priority queue，简称 PQ)分枝限界法。在优先队列分枝限界法中，用优先队列作为组织活结点表的数据结构，每个结点都有一个成本或价值，按照最大价值 (greatest value)/最小成本(least cost)的原则选择结点作为扩展结点。

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

贪心算法与分治法和动态规划算法的异同

1）分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。
2）动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。
3）贪心法与动态规划法和分治法类似，都是将问题分解为规模更小的、相似的子问题，并通过求解子问题产生一个最优解。
有些具有最优子结构性质的问题，可以用动态规划算法求解，但是用贪心算法更简单、更直接，且解题效率更高。

贪心算法与动态规划算法的主要区别所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

差异点：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

贪心算法的基本元素

贪心法自顶向下，一步一步地做出贪心选择。希望通过局部最优决策导致问题的全局最优解。

具有贪心选择的性质以及最优子结构。

哈夫曼编码：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。

分支限界法与回溯法的区别

都是在问题的解空间上搜索问题解的算法。

（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支界限法的基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法设计算法的步骤

(1)针对所给问题，定义问题的解空间（对解进行编码）；
(2)确定易于搜索的解空间结构（按树或图组织解） ；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

动态规划与备忘录算法的比较

常用的剪枝函数

1）用约束函数在扩展结点处剪去不满足约束的子树；
2）用限界函数剪去得不到最优解的子树。

矩阵连乘问题

请给出矩阵连乘问题的文字描述，然后用数学符号和公式表达出来。

什么是递归算法？递归算法的特点？两个要素？

递归方程和约束函数（递归终止条件）是递归的两个要素。

递归算法是一种直接或者间接地调用自身的算法。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

特点：

1. 每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算。（递归终止条件）
2. 递归中较小自变量函数值来表达较大自变量的函数值；（递归方程式）

适合用分治算法求解的问题具有的基本特征？

1、该问题的规模缩小到一定的程度就可以容易解决
2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3、利用该问题分解出子问题解可以合并为该问题解

动态规划算法解题步骤？

(1)刻画最优解的结构。
(2)递归定义最优解的值。
(3)自底向上(或自顶向下)方式计算最优解的值。
(4)根据计算的结果，构造问题最优解。

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2) 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3) 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4) 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

渐进表示的定义

1. 如果存在三个正常数

2. 如果存在两个正常数c，n0，对于所有的 n≥n0，有0≤f(n)≤cg(n)，则记作f(n)≤O(g(n))。

考虑算法的好坏的因素

1、执行算法所耗费的时间。
2、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
3、算法应易于理解，易于编码，易于调试等。

最优子结构

如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。

递归循环与迭代

递归是重复调用函数自身实现循环。 迭代是函数内某段代码实现循环。
迭代与普通循环的区别是：
循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

算法分析的目的

1）对算法某些特定输入，估算该算法所需的内存空间和运行时间。
2）为了建立衡量算法优劣的标准，用比较同一类问题的不同算法。

典型的解空间树：子集树和排列树

（1）当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间。
（2）当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

分支限界法的搜索策略

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

二叉查找法算法基本思想

1、将n个元素分成大致相等的两部分。
2、取A(⌊n/2⌋)与v进行比较。
3、如果相等，则找到v，返回v所在位置，算法终止；
4、如果v<A(⌊n/2⌋)，则在数组的左半部分继续查找v；如果v>A(⌊n/2⌋)，则在数组的右半部分继续查找v。
5、当所查找的区间为0时，表示v不在数组中，返回查找不成功标志0。

归并排序

1）步骤：
①划分：将待排序n个元素的序列划分成两个规模为n/2的子序列。
②解决：用归并排序递归地对每一子序列排序。
③合并：归并两个有序序列，得到排序结果。
当划分的子序列规模为1时，递归结束。因为一个元素的序列被认为是有序的。
2）归并算法描述：归并排序的关键操作是归并两个已排序的子序列的过程。用过程MERGE(A,p,q,r)表示归并两个有序序列A[p…q]和A[q+1…r]。当过程MERGE(A,p,q,r)执行完成后A[p…r]中包含的元素有序。
3）归并排序算法描述：我们将利用MERGE作为排序算法的子过程，利用MERGE-SORT对子数组A[p…r]中的元素进行排序。

calculate question

1. 某商店有 n 个物品，第 i 个物品价值为 vi，重量(或称权值)为 wi， 其中 vi和 wi为非负数。设 c［i, w］表示背包容量为 w 时，i 个物品导致的最优解的总价值。写出 0-1 背包问题的递归方程。

2. 设 l［i, j］表示序列 Xi和 Yj的 LCS 的长度，写出最长公共子序列的递归方程。

3. 使用主方法求解递归方程 T(n)=4T(n/2)+n，需写出满足主定理的哪一种情形。

解：由递归方程可得，a=4，b=2 且 f(n)=n。因此，

4. 使用递归树方法求解递归方程 T(n)=2T(n/2)+n-1，需画出完整的递归树。
   
5. 写出矩阵链乘问题的递归方程。假设最优加括号方式将乘积 AiAi+1…Aj分裂为 AiAi+1…Ak和 Ak+1Ak+2…Aj，其中 i≤k<j，设 m[i, j] 表示计算 Ai…j所需的最少乘法次数。
   
6. 算法的定义
   
7. 欧几里得算法。

GCD（n，m）
If m=0
Return n
Return（ GCD m n mod m）

8. Strassen算法递归方程。

T(n)= O(1)… n=2
T(n)= 7T(n/2)+O(n2)…n>2

9. 设A=（5，7，12，25，34，37，43，46，58，80，92，105），推导出查找元素34的变量low，high和mid的运行轨迹。

10. 自然地导出递归的斐波那契过程 F(n)

F(n)
1 if n≤2
2 then return 1
3 return F(n-1)+F(n-2)

11. 分治法计算时间的递归方程:
    
12. 活动选择问题的递归方程

13. 矩阵链乘问题的最优解

14. 背包问题最优解

15. 活动选择问题的递归贪心算法

algorithm analysis

MergeSort

2. 

LCS

QuickSort

template<class Type>
void QuickSort (Type a[], int p, int r)
{ 
   
      if (p<r) { 
   
        int q=Partition(a,p,r);
        QuickSort (a,p,q-1); //对左半段排序
        QuickSort (a,q+1,r); //对右半段排序
        }
}

BubbleSort

分析冒泡排序法BUBBLE－SORT(A)的最佳情况和最坏情况。

1. 当输入数组正好为升序时，出现最佳情况，第4行语句不执行。
2. 当输入数组为降序时，出现最差情况，第4行语句执行n（n－1）/2次。

N皇后问题

bool Queen::Place(int k)
{ 
    //检查x[k]位置是否合法
  for (int j=1;j<k;j++)
    if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
  return true;
} 

void Queen::Backtrack(int t)
{ 
   
  if (t>n) sum++;
  else    
  	for (int i=1;i<=n;i++) { 
   
      x[t]=i;
      if (约束函数) Backtrack(t+1);
    }
}

最大团问题

void Clique::Backtrack(int i) // 计算最大团
{ 
     
	if (i > n) { 
    // 到达叶结点
      for (int j = 1; j <= n; j++) bestx[j] = x[j];
      bestn = cn;   return;}
 // 检查顶点 i 与当前团的连接
   int OK = 1; 
   for (int j = 1; j < i; j++)
      if (x[j] && a[i][j] == 0) { 
            // i与j不相连
         OK = 0;  break;}

   if (OK ) { 
    // 进入左子树
      x[i] = 1;  cn++;
      Backtrack(i+1);
      x[i] = 0; cn--;  }
   
  if (cn + n - i > bestn) { 
    // 进入右子树
      x[i] = 0;
      Backtrack(i+1);  }
}

design question

2. 写出用动态规划解矩阵链乘问题的递归定义和最优解值的伪代码程序。

3. 写出哈夫曼编码的过程

理论加实践缺一不可，二者决定你走的深度与高度。

加油！

淦!