算法总习题总结

总习题记得哪些算法复杂性的知识？用自己的话简述。例如最坏时间复杂性、复杂性渐进性态的阶算法复杂性，说得简单点，运行带有这个算法的程序，消耗的电脑的资源越多，就是复杂性越高的算法；相反，如果消耗的资源很少，则是复杂性很低的算法。我们如果要把算法的复杂性具体化，一般看两个方面：时间复杂性——运行这个算法需要消耗的时间，空间复杂性——运行这个算法需要消耗的（内存）空间。我们通常所说的最坏时间复杂性就是我们一个算法预估运行消耗时间的上界，它和这个问题的规模有关，表示出来就是我们的大O表示法。我们三种常用表示法分别代表最好、最坏和平均。一般我们最看重最坏时间，但是有的时候我们需要也需要看重平均时间。举个例子：快速排序，事实证明是一个很牛很快很靠谱的排序算法，虽然它在最坏情况下就退化成了冒泡排序，也就是需要O(n2)，但是它平均时间复杂度是O(nlogn)。所以我们都需要综合考量一个算法的时间复杂度。说到渐进阶和其之间的关系，这个图已经很明白了：算法的时间复杂性分析1、如何根据算法的结构分析算法的时间复杂性？例如选择基本运算步骤、依据算法的结构统计。我们既然是根据算法的结构分析，就是一种估算，我们分析其复杂性，只联系与算法的工作量，也就是问题的规模。因此我们需要知道，首先一个算法是由控制结构（三大类型语句）和原操作组成的。所以我们要从算法中选取一个对于问题本身是一个基本运算的原操作，通过计算对原操作的重复执行的次数来度量一个算法的时间复杂性（当然我们有时候遇到的某些问题有多个原操作，那么就需要对多个原操作进行分别计算统计）。举个例子，计算两个N*N矩阵的乘积，我们需要对对应每行每列的每个元素进行相乘并且累加，也就是三层N次循环，显然相乘是一个原操作，那么T(n)=O(n3)。2、分析递归算法的方法，归方程方法和递归树。姐递归方程有迭代法（递推）法解递归方程，或套用公式，（三个公式和Master定理。）递归树的方法需利用树的基本概念求树高或树的总结点数。T(1)=1.a、b、c为常数，且a=2,b=1,c=2.（1）T(n)=aT(n-1)+bn（2）T(n)=aT(n/2)+bn显然T(n)=anT(1)+(a+....+an-1)*bn=2n+(2n-2)n=O(n2n)显然T(n)=alognT(1)+(a+....+alogn-1)*bn=2logn+(2logn-2)n=O(n2logn)3、常见算法的时间复杂性，例如快速排序、归并排序、折半查找、最小生成树，多段图。快速排序：T(n)=O(nlogn)归并排序：T(n)=O(nlogn)折半查找：T(n)=O(logn)最小生成树：T(n)=O(n2)【使用矩阵】T(n)=O(|E|logn)【使用最小堆】多段图：T(n)=O(n2)【使用动态规划】算法策略思考学习了分治法、动态规划、贪心法、回溯法、分支限界的思考策略、基本原理后，你的收获是什么？是否改变了看问题的角度和思维方式？我的收获是我们不能局限于一种问题，对于同一个问题我们也可以从多个角度采用不同的方法去解决。简而言之就是具体问题具体分析，抓住基本点，看透问题本质，从而选择合适的方法去解决。分治法的基本步骤？学过哪几种分割子问题的方法，各有什么特点？分析时间复杂性的方法。基本步骤：把大问题分成小问题求解，搞定之后，再归并成原问题的解。分割方法：（1）平均分割（折半）或者说多层分割下的均匀分割（2）随机分割，从而避免坑人的极端情况深度优先和广度优先搜索的策略比较。深度优先：深度优先搜索所遵循的搜索策略是尽可能“深”的搜索图。1）对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探寻下去。2）当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。3）这一过程一直进行到已发现从源结点可达的所有结点为止。4）如果还存在未被发现的结点，repeat，untilallpointshavebeenscanned。广度优先：广度优先搜索所遵循的搜索策略是尽可能“广”的搜索图。1）发现了新的顶点，如果还有以自己为起点而未探测到的边，就沿此边继续探寻下去。2）当自己的所有边都己被探寻过一次，通过FIFO或者LIFO等方法选择一个刚才已经探寻过的点作为起点继续走下去3）这一过程一直进行到发现每独立层单位的所有点位置。4）如果还存在未被发现的结点，repeat，untilallpointshavebeenscanned。分支限界策略和回溯法的差别？对于给定的实例如何设计搜索策略？目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解或最优解。搜索方式：回溯法以DFS搜索解空间树，而分支限界法则以BFS或以LCS搜索解空间树。看实际问题，如果需要找一个最优解就用分支限界算法，如果要找出所有解则使用回溯法。算法的流程和设计特点设计动态规划算法包含哪些关键步骤？动态规划方程的含义？对于给出的实例，如何自底向上求解？关键步骤：（1）分析最优解的性质，并刻画其结构特征，将问题分割成若干嵌套子问题。（2）递归的定义最优解，也就是找到一个状态转移方程（动态规划方程）（3）以自底向上或自顶向下的方式（保存下来逐步使用）计算出最优值（4）构造问题的最优解动态规划方程：动态规划方程可以方便了解递归过程，从而进行自底向上规划。如何自底向上：举个例子，矩阵连乘问题里面，整个的矩阵链是由两个小矩阵链相乘得到，而每个小矩阵链又是由更小两个的矩阵链相乘得到，如果我们保存每一个小矩阵链相乘的最优解，从两个相邻矩阵开始计算，那么我们就可以通过他们得到更大的矩阵链相乘的最优解，从而得到全局最优解。这个过程就是自底向上。贪心法的基本策略和算法的基本流程。问题：贪心法是不是一定有最优解？基本策略：根据最优选择性质，确定最优量化指标，将输入排序，依次选择当前最优的对象，最后达到全局最优。基本流程：（1）建立数学模型来描述问题。（2）把求解的问题分成若干个子问题。（3）对每一子问题求解，得到子问题的局部最优解。（4）把子问题的解局部最优解合成原来解问题的一个解。显然，贪心法不一定有最优解：举个例子，硬币兑换问题，我们有0.11、0.05、0.01三种，我们需要最少的硬币数量。如果我们要找出一个一个0.15的零钱，如果我们要用贪心法需要5个硬币（0.11+4*0.01），显然最优解是0.05*3对吧。回溯法算法的结构和运用条件。结构：使用DFS结构和解空间树：从x1开始搜索，如果取值满足约束，则扩展搜索。如果找不到满足约束的xk，当前扩展节点不满足约束函数，则终止搜索这棵子树，回溯到父节点。运用条件：凡是复杂的，规模较大的能构建解空间树问题都可以使用回溯法来提高效率。NP完全理论基本问题是什么？为什么值得研究？基本问题就是求解“NP=P？”，也就是NPC问题是否能在一个多项式时间内转化成一个P问题，说白了就是能不能给一个NPC问题找到一个能以多项式时间解决的解。这个问题如果研究出来，证明了NP=P，那么我们将可以把那些难的问题转化成易解的问题，从而极大地提高运算效率，解决问题将会很容易。NPC问题、NP问题和P问题是什么关系？NP完全问题是求NP中判定问题的一个子类.如果其中的任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题。NP问题，全称：多项式复杂程度的非确定性问题，是一个判定类问题的集合。有些问题很难找到多项式时间的算法（或许根本不存在），但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确的话，这类称为NP问题。也就是可以在多项式时间内验证一个解是否正确的问题称为NP问题。P问题也是一个判定类问题的集合，是可以用一个确定性算法在多项式时间内判定或解出的一类问题。简而言之，P问题就是所有复杂度为多项式时间的问题的集合。NPC问题有多难？首先难或不难看的主要是能不能在一个多项式时间内搞出来一个解。