算法分析与设计
时间：2024-01-21 23:30:01 | 来源：信息时代
时间：2024-01-21 23:30:01 来源：信息时代
1.算法：是将转入转换成输出的计算步骤所组成的序列或描述输入输出关系的特定计算过程。
2.算法正确性：对每一个输入实例算法都能终止，并给出正确输出。
算法正确性有两个要素；1是能够终止。2是结果正确。
算法设计和分析的步骤可概括:
（1）问题的陈述（2）模型的选择（3）算法的设计（4）算法的程序实现（5）算法分析。
算法具有以下五大特性
（1）确定性（2）有穷性（3）可行性（4）输入（5）输出。
循环不变式具有以下三个性质： 初始：在循环的第一次迭代之前，循环不变式为真。 维持：如果在循环的某次迭代之前循环不变式为真，那么在下一次迭代之前，循环不变式仍然为真。 终止：当循环终止时，循环不变式给出有用性质，这个性质可以用于证明算法的正确性
3.算法分析：是指对一个算法所需要的计算机资源进行预测。
考虑算法的好坏主要有以下几点：（1）执行算法所耗费的时间。（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。（3）算法应易于理解，易于编码，易于调试等。
最重要的计算资源是时间和空间资源(存储器)
输入规模是输入元素的个数、用二进制表示的输入的总位数、和用图中顶点数和边数表示输入。4.运行时间：是指在某个输入时，算法执行操作的次数或者步数。
影响程序运行时间的主要因素 ：（1）程序的输入（2）由编译系统所产生的代码程序的质量（3）执行程序的计算机机器指令的性能与速度（4）程序所依据的算法的时间复杂度。5.最坏情况：是指算法的运行时间是任一输入运行时间的上界。
算法最坏情况下的运行时间，即对于规模n的任何输入，算法运行最长的时间。之所以这样，是由于以下三个原因：1、算法的最坏情况运行时间是任一输入运行时间的上界 2、对于某些算法，最坏情况经常出现 3、算法的“平均情况”性能常常与最坏情况大致相同。
6.渐进表示：是方便地表示算法的最坏情况下，计算的复杂度。
算法的复杂性测度主要有两个方面：(1) 空间复杂度 (2) 时间复杂度 7.递归：对自己的调用。
8.动态：是所作的决策可能依赖当前状态，而此前所作的决策无。
9.规划：意味着一系列的决策。
动态规划算法的研制可由4步组成：(1)刻画最优解的结构(2)递归定义最优解的值(3)以自底向上(或自顶向下)的方式计算最优解的值(4)根据计算的结果，构造问题最优解。
10.前缀码：如果我们只用0／1对字符进行编码，并限定任一字符的编码都不是另一个字符编码的前缀，则称这样的编码为前缀码
11.哈夫曼编码：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。
12.最优子结构:如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。
13.贪心选择的性质:通过局部最优选择(贪心)，可以得到问题的全局最优解。
14．在矩阵链乘问题中，能对矩阵进行分割的叫非平凡矩阵链乘。
15．在矩阵链乘问题中，不能对矩阵进行分割的叫平凡矩阵链乘。
16．动态规划算法的运行时间取决于两个因素的乘积:
17．特点：此方法的主要特点是通过采用表格技术。计算所有子问题的解。计算的过程从小问题到大问题，并将计算结果存储在一张表中。
18．优点：一旦一个子问题被解决，就存储其结果，此后遇到同样的子问题，就不再重复计算。用多项式算法代替指数算法。
19．应用：动态规划典型的应用领域是组合优化问题。
-
网站
-
营销
-
设计
-
运营
-
优化
-
效率
-
专注
-
电商
-
方案
-
推广
微信公众号
版权所有© 亿企邦 1997-2025 保留一切法律许可权利。
在线咨询