算法导论期末复习

2024-07-09 15:47| 来源: 网络整理| 查看: 265

算法

期末复习的时候记的笔记，分享给大家~

第二章算法基础

为了解决一个给定的问题算法一次或多次的递归调用其自身以解决紧密相关的若干子问题。遵循分治的思想:将原问题分解为几个规模娇小但类似于原问题的子问题，递归求解子问题，合并子问题的解来建立原问题的解。

分析算法，要有一个模型，描述所用资源极其代价的模型。我们通常想度量的是计算时的运行时间。 RAM：随机存取机（RAM）计算模型。 - 指令一个接一个地执行，没有并行操作。 - 每次，程序指令都作为原子操作执行。一条指令包括算术运算，逻辑运算，数据移动和控制操作。 - 每个这样的指令都需要一定的时间。 - RAM容量足够大。

忽略高阶项的常系数和低阶项的一个很好的理由是RAM模型不是完全现实的（不是所有的操作都是相同的）。

When we say “the running time is O(n2)” we mean that the worst-case running time is O(n2) – the best case might be better.

Divide - and - Conquer ：分解，解决，合并。

主定理

Insert Sort Algorithm：具有空间原址性插入排序最坏情况运行时间θ(n^2)，Best-case linear in Ω(n), worst-case quadratic in O(n2) >> Best case: Ω(n) – when the input array is already sorted. >> Worst case: O(n2)– when the input array is reverse sorted. >> We can also say that the worst case running time is Ω(n^2)

循环不变式：loop-invariants

1、初始化：循环的第一次迭代之前它为真。【j=2时A[1]是按序排好的，第一次迭代之前循环不变式成立。】 2、保持：如果循环的某次迭代之前它为真，那么下一次迭代之前它仍为真。【A[1…j]是按序排列的，for循环的下一次迭代之前j将保持循环不变式】 3、终止：在循环终止时，不变式为我们提供一个有用的性质，有助于证明算法是正确的。【当j=n+1时，循环终止，A[1…n]已按序排列，就是整个数组，所以整个数组已排序，因此算法正确。】

Merge Sort Algorithm ：不具有空间原址性

归并排序事θ(nlgn)以2为底:递归式的T(n)是表示运行时间，n表示规模，它的总代价:由于总共lgn+1层，每层代价为cn，所以总代价为cn*lgn+cn，忽略低阶项和常量C便得出期望E的结果θ(nlgn)。

算法的最坏情况运行时间给出了任意输入的运行时间的一个上界，知道了这个界，就可以确保这个算法不需要更多的时间。

平均情况运行时间往往和最坏情况大致一样差。

第三章函数的增长

一旦输入规模n足够大，最坏情况运行时间为θ(nlgn)的归并排序战胜θ(n^2)的插入排序。这时使得只有运行时间的增长量级有关时，我们研究算法的渐进效率。

使用渐进记号来描述算法的运行时间，应用于函数，但是除去了某些细节。我们常常做出一种综合性的覆盖所有可能的输入而不仅仅是最坏情况的陈述。刻画任何输入的运行时间的渐进记号。 f(n) ∈/= θ/Ο/Ω(g(n))

f(n) = θ(g(n)): g(n)是f(n)的一个渐进紧确界（asymptotically tight bound） θ记号限制一个函数在常量因子内。 f(n) = O(g(n)): O记号为函数给出一个常量银子内的上界。 f(n) = Ω(g(n)): Ω记号为函数给出一个常量因子内的下界。存在√正常量n0，c1，c2，当n>=n0 c1g(n)0，有f(n) = Ω(n^((logba)+ε))，且对于某个常数c That is, insert A[i] into list B[ n A[i] ] -- ② For each bucket >> sort list B[ i ] with insertion sort -- ③ concatenate(连接) the list B[0], B[1],…,B[n - 1] together in order Total time to examine all buckets in line 5 is O(n), without the sorting time.

排序算法总结

Sorting methods Worst Case Best Case Average Case Application Insert Sort n2 n n2 Very fast when n=2 = e2 + a2,1 j=1

Matrix-Chain Multiplication 矩阵链乘的次数s

a. 时间复杂度O(n^3) 维护一个二维数组m[i][j] [p*q] X [q*r] 相乘次数为pqr 最优子结构：如果最优的加括号方式将其分解为 A i..k 与A k+1..j 的乘积，则分别对 A i..k 与 A k+1..j 加括号的方式也一定是最优的。 -- 可以利用剪切－粘贴的方式证明最优子结构性质。（唯一需要确定的就是 k 的值）最优子结构：递归公式： m[i,j] = 0 i=j =min﹛m[I,k] + m[k+1,j] + pi-1*pk*pj﹜ i< j m[i,j]: Ai到Aj之间最少的相乘次数 p1代表的是A1的列数，A2的行数 p0代表的是A1的行数… A代表矩阵，Ai ： [pi-1] * [pi]

optimization Problems：最优化问题

相比于自上而下，自底向上比较好。步骤： 1、刻画/描述最优解的结构特征； 2、递归地定义最优解的值。 3、以自下而上的方式计算方案的值。 4、使用已经计算的信息构造一个最优解。 a. Shortest path has optimal substructure b. Longest path does not have optimal substructure

重叠子问题：

存储在子问题中求解过的选择。

§ Bottom-up dynamic programming algorithm – More efficient » regular pattern of table access can be exploited to reduce time or space » take advantage of the overlapping-subproblems property. § Top-down recursive algorithm » repeatedly resolve each subproblem each time it appears in the recursion tree. » recursion overhead » Only work when the total number of subproblems in the recursion is small.

来记忆自然但效率低下的递归算法。

记忆递归算法在表格中维护每个子问题的解决方案。最初包含一个特殊值，用于指示条目尚未填充。当在执行递归算法期间首次遇到子问题时，计算其解决方案，然后将其存储在表中。

Longest Common Subsequence 最长公共子序列

时间复杂度 O(mn) ，打印结果的时间复杂度O(m+n)维护一个二维数组c[i][j]

剪切粘贴法？？？ —— If z=LCS(x,y), then any prefix of z is an LCS of a prefix of x and a prefix of y .

会有重叠子问题，故要记录子问题的解。 solving subproblems already solved The number of distinct LCS subproblems for two strings m and n is only mn .

Max Sum 连续数字最大和

维护一维数组t[j]

t[j] = max(t[j-1]+A[j],A[j] ), 1wi = c[i-1,w] wi>w = 0 w或i=0 The boundary conditions are c[0, j] = 0 if j ≥ 0, and c[i, j] = −∞ when j < 0.

3、Huffman coding 哈夫曼编码 The idea is that we will use a variable length code instead of a fixed length code (3 bits for each character), with fewer bits to store the common characters, and more bits to store the rare characters.

左小右大，依次选择最小的两个数生成父节点

单源点最短路径： Dijkstra’s algorithm: O(E+VlgV) Bellman-Ford: O(VE) Floy-Warshall algorithm cij(k)=mink{cij(k-1),cik(k-1)+ckj(k-1)}

第二十四章最短路径

单源点最短路径

无负边 >>Dijkstra 算法: O(E+VlgV)一般情况 >>Bellman-Ford: O(VE)

每对结点间最短路径

无负边 >> 执行 |V| 次 Dijkstra 算法: O(VE+V2lgV)一般情况  Run Bellman-Ford once for each vertex  d(m)ij = mink{d(m-1)ik+akj }  floyd-washall Algorithm  Johnson Algorithm 回溯法

回溯法又称试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。即从一条路往前走，能进则进，不能进则退回来，换一条路再试。这种以深度优先DFS的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题

对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果

回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。搜索过程中用剪枝函数避免无效搜索。

1、八皇后问题8-Queens

利用回溯法解题的具体步骤： (1)描述解的形式，定义一个解空间，它包含问题的所有解。 (2)构造状态空间树。 (3)构造约束函数（用于杀死节点）。扩展节点、活结点、死结点扩展节点：就是当前正在求出它的子节点的节点，在深度优先搜索中，只允许有一个扩展节点。 • 活结点：就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点； • 死结点：反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。第三十四章 NP（non-deterministic Polynomial）多项式复杂度非确定性问题

【set of decision problems solvable in polynomial time on a NONDETERMINISTIC Turing machine】 SAT is the first NP-Complete problem，satisfiability Problem布尔逻辑可满足性问题 Other NP-Complete problems: 3-color：Is there a way to assign inputs to a given Boolean (combinational) circuit that makes it true? TSP（旅行商问题）： A traveling salesperson needs to visit N cities. Is there a route of length at most D? MIS, …

【本文地址】

算法导论期末复习

算法导论期末复习

今日新闻

推荐新闻