《算法分析的复习总结》由会员分享，可在线阅读，更多相关《算法分析的复习总结（4页珍藏版）》请在金锄头文库上搜索。
1、递归：直接或间接的调用自身算法称为递归算法；用函数自身给出定义的函数称为递归函数。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法（divide-and-conquer ）的基本思想：A 分割成 k 个更小规模的子问题。 B 对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最
2、优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质贪心算法: 贪心算法总是作出在当前看来最好的选择,它并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。贪心算法：贪心算法求解的这类问题一般具有 2 个重要的性质：贪心选择性质和最优子结构性质。 贪心选择性质是指所求问题的整体
3、最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是 2 类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?单源最短路径基本思想是，设置顶点集合
4、 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S 中取出具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数组 dist 作必要的修改。一旦 S包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。回溯法的基本思想：(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构；(
5、3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常见的两种分支限界法：（1）队列式(FIFO)分支限界法。按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。布线问题算法思想：解此问题的队列式分支限界法从起始位置 a 开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为 1，即从起始方格 a 到这些方格的距离为 1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为
6、 2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格 b 或活结点队列为空时为止。即加入剪枝的广度优先搜索。随机存储机 RAM 它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM 由只读输入带、只写输入带、程序存储部件、内存储器和指令计数器 5 个部分组成。 P 类和 NP 类语言的定义 P=L|L 是一个能在多项式时间内被一台 DTM 所接受的一眼 NP+L|L 是一个能在多项式时间内被一台 NDTM 所接受的语言 由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故 P 属于NP P 类问题： 是确定性计算模型下的易解问
7、题类。NP 类问题：是非确定性计算模型下的易验证问题类。NP 完全类问题：即多项式复杂度的非确定性问题类；简单的写法是 NP=P？问题就在这个问号上，到底是 NP 等于 P，还是 NP 不等于 P。算法的渐进时间复杂性的含义？答：当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是 T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用 T(n)的数量级 (阶)评价算法。时间复杂度 T(n)的数量级(阶) 称为渐进时间复杂性。最坏情况下的时间复杂性和平均时间复杂性有什么不同？答：最坏情况下的时间复杂性和平均时间复杂性考察的是 n 固定时，不同输入实例下的算法所耗时间。最坏情况下
8、的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n，I) , IDn A(n) =P(I)T(n ，I) IDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：采用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为 n 元组：（x1,x2,xn） ，xi Si, Si 为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x2,xi）(i amiddle) left = middle + 1;else right = middle - 1;return -1; 棋盘覆盖public void chessBo
9、ard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, s = size/2; if (dr = tc + s)chessBoard(tr, tc+s, dr, dc, s);else boardtr + s - 1tc + s = t;chessBoard(tr, tc+s, tr+s-1, tc+s, s);if (dr = tr + s & dc = tr + s & dc = tc + s)chessBoard(tr+s, tc+s, dr, dc, s);else board
10、tr + stc + s = t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);三、动态规划最长公共子序列void LCSLength(int m，int n， char x，char y，intc， int b) int i，j;for (i = 1; i =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; 构造最长公共子序列void LCS(int i，int j，char *x ，int *b) if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); cout n) r -= wi; if (cw + wi bestw) xi = 0; backtrack(i + 1); r += wi; 批处理问题：void Flowshop:Backtrack(int i)if (i n) for (int j = 1; j f1)?f2i-1:f1)+Mxj2;f+=f2i; if (f N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E); catch (OutOfBounds) break;
