新颖版_南邮《算法分析报告与设计》考点2014

《新颖版_南邮《算法分析报告与设计》考点2014》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档第一章算法求解基础l算法特征（输入、输出、确定性、可行性、有穷性）l描述算法的方法（自然语言、流程图、伪代码、程序设计语言）l欧几里德算法（辗转相除法）——递归/迭代（实现）——求最大公约数l常见算法种类——精确算法、启发式算法、近似算法、概率算法l数学归纳法证明；第二章算法分析基础l算法复杂度——运行一个算法所需的时间和空间。l好算法的四个特征（正确性、简明性、效率、最优性）正确性vs健壮性vs可靠性最优性——算法（最坏情况下）的执行时间已达到求解该类问题所需时间的下界。l影响程序运行时间的因素（程序所依赖的算法、问题规模和输入数据、计算机

2、系统性能）l算法的渐近时间复杂度——数量级上估计（Ο、Ω、Θ）l最好、最坏、平均时间复杂度——定义——课后习题2-8（通过考察关键操作的执行次数）l时间复杂度证明——课后习题2-10，2-13，2-17文案大全实用文档l算法按时间复杂度分类：多项式时间算法、指数时间算法多项式时间算法：O(1)

3、而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止；最后将子问题的解组合成原始问题的解。这种问题求解策略称为分治法。l分治法很自然的导致一个递归算法。l平衡子问题思想l递归算法的时间复杂度分析:递推式T(n)=aT(n/b)+cnk，T(1)=c求解。——改进思路l求最大最小元l二分搜索（对半搜索）——对半搜索二叉判定树的4个性质，2个定理。l二叉判定树的性质→对半搜索的时间复杂度成功搜索：平均、最坏O(logn)失败搜索：平均、最好、最坏都是Θ(logn)文案大全实用文档（通过关键字值间的比较，搜索指定关键字值元素）这类搜索算法最坏

4、情况下的时间下界为O(logn)，因此对半搜索是最优算法。——课后习题5-8l最优算法l两路合并排序——时间复杂度l快速排序——排序过程（每一趟分划后的排列和子问题划分）——时间复杂度分析（最好、最坏、平均）——课后习题5-11l斯特拉森矩阵乘法——时间复杂度的改进；l棋盘覆盖问题——算法设计思想——时间复杂度分析——最优算法第六章贪心法l贪心法算法思想——分步决策求解最优化问题——局部最优选择（最优量度标准）——得到整体最优解l贪心法的基本要素：n最优子结构性质n贪心选择性质文案大全实用文档l一般背包问题；——课后习题6-1l最佳合并模式；——带权

5、外路径长度（WPL）最小——课后习题6-8l最小代价生成树——Prim和Kruskal算法——共同的理论基础：MST性质——不同点和应用场合——课后习题6-9第七章动态规划法l（求解最优化问题）动态规划法的基本要素：n最优子结构性质n重叠子问题性质l动态规划法求解步骤：n1）刻画最优解的结构特性n2）递归定义最优解值n3）以自底向上方式计算最优解值n4）根据计算得到的信息构造一个最优解l备忘录方法（动态规划法的变形）——两者的异同和适用场合l多段图问题文案大全实用文档——从后向前/从前向后递推式——结点的cost和d值求解过程——最短路径长度，并根据

6、d值构造最短路径注意：d[j]的含义和最短路径的构造。——课后习题7-1，7-2l关键路径问题——earliest、latest的递推式和求解过程——寻找关键活动，构造关键路径——程序实现——补充题注意：应由关键活动（而不是事件i）来确定关键路径。l弗洛伊德算法——dk数组和pathk数组更新的递推式——每次迭代后的d数组和path数组元素值——程序实现和时间复杂度l最长公共子序列问题——c和s数组元素的求解递推式——c和s数组元素求值，得最优解值——回溯构造最优解——程序实现——课后习题7-9l0/1背包问题及其启发式方法求解文案大全实用

7、文档注意：被支配的阶跃点和所有X>M的阶跃点均应该去除。——课后习题7-15、补充题第八章回溯法l状态空间树——描述问题解空间的树形结构n问题状态（树中每个结点）n解状态（候选解元组）n答案状态（可行解元组）n最优答案结点（目标函数取最优值的答案结点）l剪枝函数（约束函数、限界函数）n约束函数——剪去不含答案状态（可行解）的子树n限界函数——剪去不含最优答案结点的子树l约束函数（显式约束、隐式约束）n显示约束——规定了所有可能的元组，组成问题的候选解集（解空间）l排列树——用于确定n个元素的排列满足某些性质的状态空间树，一般有n!个叶结点（解状态）。

8、l子集树——从n个元素的集合中找出满足某些性质的子集的状态空间树，一般有2n个解状态。n隐式约束——给出了判