算法分析与设计基本知识点复习省公开课一等奖全国示范课微课金奖课件

算法

算法(algorithm)能够被定义为一个良定计算过程，它含有一个或者若干输入值，并产生一个或者若干输出值。人们采取普通术语陈说问题，确定输入／输出关系，而算法则是描述这种输入／输出关系特定计算过程。算法正确性：对每一个输入实例算法都能终止，并给出正确输出。算法正确性有两个要素；1是能够终止。2是结果正确。1/30算法设计和分析步骤可概括:（1）问题陈说。（2）模型选择。（3）算法设计。（4）算法程序实现。（5）算法分析。2/30算法含有以下五大特征（1）确定性。一个算法中给出每一个计算步骤，必须是准确定义、无二义性。（2）有穷性。一个算法在执行有穷个计算步骤后必须停顿。（3）可行性。算法中要执行每一个计算步骤都是能够在有限时间内做完。可行性、有穷性和确定性是相容。（4）输入。一个算法普通都要求一个或多个输入信息。（5）输出。一个算法普通有一个或多个输入信息。它们通常能够被解释成为“对输入计算结果”。3/30循环不变式含有以下三个性质：初始：在循环第一次迭代之前，循环不变式为真。维持：假如在循环某次迭代之前循环不变式为真，那么在下一次迭代之前，循环不变式依然为真。终止：当循环终止时，循环不变式给出有用性质，这个性质能够用于证实算法正确性4/30循环不变式：A[j]是A[j..Length[A]]中最小元素。循环不变式：在1～4行外层for循环每次迭代开始，子数组A[1..i-1]中元素有序。5/30算法分析(p4)算法分析是指对一个算法所需计算资源进行预测。考虑算法好坏主要有以下几点：（1）执行算法所花费时间。（2）执行算法所花费存放空间，其中主要考虑辅助存放空间。（3）算法应易于了解，易于编码，易于调试等。

最主要计算资源是时间和空间资源(存放器)输入规模是输入元素个数、用二进制表示输入总位数、和用图中顶点数和边数表示输入。一个算法运行时间是指在某个输入时，算法执行基本操作次数或者步数。6/302、影响程序运行时间主要原因：（1）程序输入。（2）由编译系统所产生代码程序质量。（3）执行程序计算机机器指令性能与速度。（4）程序所依据算法时间复杂度。3、算法复杂性测度主要有两个方面：(1)空间复杂度(2)时间复杂度7/30最坏情况和平均情况分析(P6)算法最坏情况下运行时间，即对于规模n任何输入，算法运行最长时间。之所以这么，是因为以下三个原因：1、算法最坏情况运行时间是任一输入运行时间上界。2、对于一些算法，最坏情况经常出现。3、算法“平均情况”性能经常与最坏情况大致相同。8/30渐近表示(P8)渐进表示：是方便地表示算法最坏情况下，计算复杂度。

三个定义，三例题。定义1．1假如存在三个正常数9/3010/30第2章分治法

递归(P13)递归程序可被简单地定义为对自己调用。递归程序要求必须有终止条件。斐波那契(Fibonacci)序列。替换方法(P16)用替换方法解某个递归方程时，分为两步。首先猜测问题解某个界限，然后用数学归纳法证实所猜测解正确性。主方法(P18)主定理（三种情况，三个例题）11/30分治法基本思想

(p20)

分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同子问题。(2)处理(conquer)：若子问题规模较小，则直接求解；不然递归求解各子问题。(3)合并(combine)：将各子问题解合并为原问题解。12/30算法思想假如我们将分治策略用于此问题，每次将问题分成大致相等两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题解组合成原问题解，就可得到该问题分治算法。归并排序算法(P28)归并排序关键操作是归并两个已排序子序列过程。找最大值与最小值分治算法13/30归并排序最坏情况下时间复杂度Θ(nlbn)要优于冒泡排序最坏情况下时间复杂度Θ(n2)。14/30动态规划（P49）

动态规划(dynamicprogramming)已经成为计算机科学中主要算法设计范型。

1、提出：1957年，RichardBellman在描述一类优化控制问题时创造了这个名字。

2、作用：那时，这个名字更多地用于描述问题，而不是解问题技巧。15/30

3、特点：此方法主要特点是经过采取表格技术。计算全部子问题解。计算过程从小问题到大问题，并将计算结果存放在一张表中。

4、优点：一旦一个子问题被处理，就存放其结果，今后碰到一样子问题，就不再重复计算。用多项式算法代替指数算法。16/30

5、应用：动态规划经典应用领域是组合优化问题。在这类问题中，可能会有许多可行解(feasiblesolution)，每个解对应一个值，我们想要找出一个含有最优值解，称这个解为问题一个最优解。可能有多个解都到达这个最优值。

6、概念：

规划(programming)含义意味着一系列决议；动态(dynamic)含义则传递着这么一个思想，就是所做决议可能依赖于当前状态，而与以前所做决议无关。

17/30约束条件为1表示第i个物品选中,0为第i个物品没选中。0-1背包问题(52)目标18/300-1背包问题最优解结构：设X=(x1,x2,…,xn)是一个最优解，其结构为：

1、这个包含第n个物品时，即xn=1,则x1,x2,…,xn-1，W-wi为子问题最优解。2、这个不包含第n个物品时，即xn=0,则x1,x2,…,xn-1，W为子问题最优解矩阵链乘问题最优结构。

19/30非平凡矩阵链乘：在矩阵链乘中能够进行分割矩阵链乘。平凡矩阵链乘：在矩阵链乘中不能进行分割矩阵链乘。非平凡矩阵链乘问题都会对矩阵进行分割，而分割位置是未定，需要我们确定

。20/30动态规划算法研制可由4步组成：(1)刻画最优解结构。(2)递归定义最优解值：(3)以自底向上(或自顶向下)方式计算最优解值。(4)依据计算结果，结构问题最优解。

21/30动态规划基本元素(p60)动态规划应用于组合优化问题时，问题本身应有两个特点。这就是问题含有最优子结构和重合子问题。

1．最优子结构动态规划应用于组合优化问题第一个特征是问题本身含有最优子结构。

假如问题最优解包含子问题最优解，则问题展示了最优子结构。22/30只要问题展示最优子结构，就为应用动态规划提供了可能性。

在寻找问题最优子结构时，问题含有以下公共结构：(1)问题解由一系列决议组成。(2)对于给定问题，假定已知一个选择造成最优解。不需关心如荷做出这个选择，只需假定它是已知。23/30(3)给定这个决议，你来决定哪些子问题最好地刻画子问题其余空间。(4)证实在问题最优解中所用到子问题解，经过使用“切割一粘贴”技术，一定是最优。刻画子问题空间标准是,尽可能保持这个空间简单,然后在需要时候扩展它。24/30

最优子结构随问题域改变有两种方式：(1)原问题最优解中,利用了多少个子问题?(2)决定最优解中使用哪些子问题需做多少次决议?在0-1背包问题中,最优解利用两个子问题，即c[i-1,w]和c[i-1,w-wi]。在矩阵链乘子问题最优解利用两个子问题。这是因为,对于在矩阵某处罚裂Ak,产生两个子问题：AiAi+1…Ak加括号方式和Ak+1Ak+2…Aj加括号方式,我们必须最优处理这两个子问题。25/30自顶向下动态规划方法含有以下特点：

·它是一个对自然问题求解机械转换。·方法本身能够确定计算子问题次序。·可能不需要计算出全部子问题解。备忘录方法(64)2．重合子问题动态规划应用于组合优化问题第二个特征是问题本身含有重合子问题。动态规划算法运行时间取决于两个原因乘积:26/30第4章贪心法(p98)

贪心法当前选择可能要依赖已经做出全部选择，但不依赖于有待于做出选择和子问题。贪心法自顶向下，一步一步地做出贪心选择。贪心法总是做出在当前时刻看起来最优决议，即希望经过局部最优决议造成问题全局最优解。贪心法并不总是产生问题全局最优解，但许多问题利用贪心法求解得到全局最优解。27/30约束条件为：背包问题(p98)可行解即满足约束条件解

用贪心策略求解背包问题时，首先要选出度量标准。取目标函数作为度量标准，即每放入一件物品使背包取得最大可能效益值增量。按物品权重非降次序把物品放入背包。用每单位容量所带来价值之比作为贪心策略，能够得到问题最优解。

28/30分几步求解这个问题。首先找出该问题动态规划解，组合两个子问题解成原问题解。

在决定最优解中选择哪个子问题，考虑几个选择。经过贪心选择策略,我们只需要选择一