算法分析与设计知识点总结.docVIP

第一章 概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章 递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念： 直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。 反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 第三章 动态规划 动态规划的基本思想： 动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个阶段或子问题的解就是初始问题的解。 分治法求解时，子问题数目太多，从而导致解决原问题需要耗费指数级时间。 与分治法不同的是，动态规划中分解得到的子问题往往不是互相独立的。 但不同子问题的数目常常只有多项式级。用分治法求解时，有些子问题被重复计算了许多次。 动态规划的适用条件： 动态规划法解所能解决的问题一般具有以下两个基本因素： 一、最优子结构性质 当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。 二、重叠子问题性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 其它同分治法。 动态规划问题的特征： 求解的问题是组合优化问题； 求解过程需要多步判断，从小到大依次求解； 子问题目标函数最优解之间存在依赖关系； 动态规划算法设计的基本步骤和要素： 基本步骤： （1）找出最优解的性质，并刻画其结构特征。（考察是否适合采用动态规划法。） （2）递归地定义最优值。(建立递归式或动态规划方程) （3）以自底向上的方式（或以自顶向下的备忘录方法）计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 要素： 最优子结构 重叠子问题 备忘录（表格） 应用实例分析： 1、矩阵连乘问题：