算法分析与设计基本知识点复习

《算法分析与设计基本知识点复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法算法(algorithm)可以被定义为一个良定的计算过程，它具有一个或者若干输入值，并产生一个或者若干输出值。人们采用一般术语陈述问题，确定输入／输出关系，而算法则是描述这种输入／输出关系的特定计算过程。算法正确性：对每一个输入实例算法都能终止，并给出正确输出。算法正确性有两个要素；1是能够终止。2是结果正确。算法设计和分析的步骤可概括:（1）问题的陈述。（2）模型的选择。（3）算法的设计。（4）算法的程序实现。（5）算法分析。算法具有以下五大特性（1）确定性。一个算法中给出的每一个计算步骤，必须是精确的定义、无二义性的。（2）有穷性。一个

2、算法在执行有穷个计算步骤后必须停止。（3）可行性。算法中要执行的每一个计算步骤都是可以在有限时间内做完的。可行性、有穷性和确定性是相容的。（4）输入。一个算法一般都要求一个或多个输入信息。（5）输出。一个算法一般有一个或多个输入信息。它们通常可以被解释成为“对输入的计算结果”。循环不变式具有以下三个性质：初始：在循环的第一次迭代之前，循环不变式为真。维持：如果在循环的某次迭代之前循环不变式为真，那么在下一次迭代之前，循环不变式仍然为真。终止：当循环终止时，循环不变式给出有用性质，这个性质可以用于证明算法的正确性循环不变式：A[j]是A[j..L

3、ength[A]]中的最小元素。循环不变式：在1～4行外层for循环的每次迭代开始，子数组A[1..i-1]中的元素有序。算法分析(p4)算法分析是指对一个算法所需的计算资源进行预测。考虑算法的好坏主要有以下几点：（1）执行算法所耗费的时间。（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。（3）算法应易于理解，易于编码，易于调试等。最重要的计算资源是时间和空间资源(存储器)输入规模是输入元素的个数、用二进制表示的输入的总位数、和用图中顶点数和边数表示输入。一个算法的运行时间是指在某个输入时，算法执行基本操作的次数或者步数。2、影响程序

4、运行时间的主要因素：（1）程序的输入。（2）由编译系统所产生的代码程序的质量。（3）执行程序的计算机机器指令的性能与速度。（4）程序所依据的算法的时间复杂度。3、算法的复杂性测度主要有两个方面：(1)空间复杂度(2)时间复杂度最坏情况和平均情况分析(P6)算法最坏情况下的运行时间，即对于规模n的任何输入，算法运行最长的时间。之所以这样，是由于以下三个原因：1、算法的最坏情况运行时间是任一输入运行时间的上界。2、对于某些算法，最坏情况经常出现。3、算法的“平均情况”性能常常与最坏情况大致相同。渐近表示(P8)渐进表示：是方便地表示算法的最坏情况下

5、，计算的复杂度。三个定义，三例题。定义1．1如果存在三个正常数第2章分治法递归(P13)递归程序可被简单地定义为对自己的调用。递归程序要求必须有终止条件。斐波那契(Fibonacci)序列。替换方法(P16)用替换方法解某个递归方程时，分为两步。首先猜测问题解的某个界限，然后用数学归纳法证明所猜测解的正确性。主方法(P18)主定理（三种情况，三个例题）分治法的基本思想(p20)分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer)：若子问题规模

6、较小，则直接求解；否则递归求解各子问题。(3)合并(combine)：将各子问题的解合并为原问题的解。算法思想如果我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。归并排序算法(P28)归并排序的关键操作是归并两个已排序的子序列的过程。找最大值与最小值分治算法归并排序最坏情况下的时间复杂度Θ(nlbn)要优于冒泡排序最坏情况下的时间复杂度Θ(n2)。动态规划（P49）动态规划(dynamicprogramming)已经成为计算机科学中重要

7、的算法设计范型。1、提出：1957年，RichardBellman在描述一类优化控制问题时创造了这个名字。2、作用：那时，这个名字更多地用于描述问题，而不是解问题的技巧。3、特点：此方法的主要特点是通过采用表格技术。计算所有子问题的解。计算的过程从小问题到大问题，并将计算结果存储在一张表中。4、优点：一旦一个子问题被解决，就存储其结果，此后遇到同样的子问题，就不再重复计算。用多项式算法代替指数算法。5、应用：动态规划典型的应用领域是组合优化问题。在这类问题中，可能会有许多可行解(feasiblesolution)，每个解对应一个值，我们想要找出

8、一个具有最优值的解，称这个解为问题的一个最优解。可能有多个解都达到这个最优值。6、概念：规划(programming)的含义意味着一系列的决策；动态(