○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
边界条件与递归方程是递归函数的二个要素应用分治法的两个前提是问题的可分性和解的可归并性以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。
回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
舍伍德算法设计的基本思想:设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。
设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得的可能性。
希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有拉斯维加斯( Las Vegas )算法的基本思想:设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。
一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。
设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得：蒙特卡罗(Monte Carlo)算法的基本思想:设p是一个实数，且1/2<p<1。
如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。
如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。
线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。
单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m或n次迭代就可求得最优解。
单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。
每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。
图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。
NPC形式化定义：定义1：语言L是NP完全的当且仅当（1） L【NP；（2）对于所有L’【NP有L’ ～pL。
如果有一个语言L满足上述性质(2),但不一定满足性质（1），则称该语言是NP难的。
所有NP完全语言构成的语言类称为NP完全语言类，就是NPC。
定理1 设L是NP完全的，则（1）L P当且仅当P＝NP；（2）若 L p L1，且 L1 NP，则L1是NP完全的。
团问题:任给图G和整数k．试判定图G中是否存在具有k个顶点的团？1)团问题NP。
显然，验证G的一个子图是否成团只需多项式时间即可。
2)SAT团问题。
任给表达式f．构造一个相应的图G如下：①图G的每个顶点对应于f中的每个文字(多次出现的重复计算)。
②若G中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。
设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。
这是因为：(a)若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1＜i<n)中一个)对应的图G中的n个顶点就构成一个团。
(b)若图G中有一n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f 的取值为真(这由图G的定义易证)。
显见，上述构造图G的方法是多项式界的，因此SAT 团问题。
由(a)、(b)有，团问题NPC。
证毕。
单源最短路径问题:void shortestpaths(v){MinHeap H[1000];x)；DeleteMin(H,E)；} .mn个向量。
解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n2n)。
贪心法解最优装载问题：template<class Type>void Loading(int x[], Type w[], Type c, int n){int *t = new int [n+1];Sort(w, t, n);for (int i = 1; i <= n; i++) x[i] = 0;for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} }算法所需的计算时间为 O(nlogn)算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列，满足性质：(1)输入 (2)输出 (3)确定性 (4)有限性：问题的计算时间下界为(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。
1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。
2. 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。
3.什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。
将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。
5、什么是NP类问题：NP={L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言}，其中NDTM是非确定性图灵机。
或者可说：NP是所有可在多项式时间内用不确定的算法求解的判定问题的集合。
对于NP类，相当于要求验证模块在多项式时间内完成对应NDTM，有非确定性算法。
1. 算法的分类：1）(数值算法 ) 2）非数值算法2. 算法的描述：1）自然语言描述 2）(流程图描述) 3）程序语言描述3. 算法的分析标准：1）时空观念 2 ）(发展观念) 3）设计观点 4）交流的观点设计动态规划算法的步骤。
(1)找出最优解的性质，并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。
动态规划法求矩阵连乘问题：void MatrixChain(int *p，int n，int **m，int **s){for (int i = 1; i <= n; i++) m[i][i] = 0;for (int r = 2; r <= n; r++)for (int i = 1; i <= n - r+1; i++) {int j=i+r-1;m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];s[i][j] = i;for (int k = i+1; k < j; k++) {int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}}}}因此算法的计算时间上界为O(n3)。
算法所占用的空间显然为O(n2)。
1.简述算法的五个重要的特征。
：①有穷性：一个算法必须保证执行有限步之后结束；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
备注：算法可以没有输入。
因为有些算法中包含了输入，如随机产生输入。
2.简答贪心算法的基本元素：①贪心选择性质：所谓贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择达到。
②最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。
3.简述动态规划算法的基本思想和基本步骤以及动态规划问题的特征。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
按以下几个步骤进行：①分析最优解的性质，并刻划其结构特征。
②递归地定义最优值。
③以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
④根据计算最优值时得到的信息，构造一个最优解。
动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。
4.简述回溯算法的基本思想及解题步骤。
回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
换句话说，这个结点不再是一个活结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
（9分）运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2分）（2）确定易于搜索的解空间结构；（2分）（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
5.简述分治算法的基本思想及基本步骤。
分治法的基本思想：对于一个输入规模为n的问题，若该问题容易的解决，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解这些子问题，然后将各个子问题的解合并，得到原问题的解。
（9分）分治法在每一层递归上由以下三个步骤组成：①划分：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；（2分）②解决：若子问题规模较小，则直接解决；否则递归求解各个子问题。
（2分）③合并：将各个子问题的解合并为原问题的解。
（2分）6.分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。