(算法分析.docxVIP

第一章算法的概念算法书中的算法特指计算机科学中的算法，即那些在计算机科学中描述为适宜于作为计算机程序执行的解决问题的方法算法 是一个有穷的规则序列。 是一个能完成特定任务的有穷指令集合。 决定了解决某一特定问题的一系列运算。 即算法是一个指令的有限集合。算法复杂性分析在“正确地”前提下，评价有两个指标：时/空 时间复杂性和空间复杂性算法程序运行时的消耗时间算法程序运行时所占用的存贮大小 最坏情况、最好情况、平均情况的复杂性如果给定输入大小，把复杂度取做所有输入（可能是有限个也可能是无限个）的最大复杂度，则称之为最坏情况复杂度；如果把复杂度取做所有输入的“平均”复杂度，则称之为平均情况复杂度（亦有称作期望时间复杂度）。在大多数情况下，我们主要研究个算法的最坏情况复杂度，因为它应用广泛，也比较容易处理 渐进复杂性的意义我们关心的一般是最坏情况下的计算时间复杂度的上界 渐近意义下的记号：O、Ω、θ T（n）= limt f(n) = ○(f(n)) 趋势，渐进时间复杂度 n→∞ ○(n)至多要用时间的数量级。 掌握算法渐进复杂性的分析学习目的：能设计出好的算法； 2)能分析评价算法的好坏第二章 递归与分治策略算法总体思想1、将问题分解成k个子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。2、将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。递归的概念直接或间接地调用自身的算法称为递归算法递归算法应用1、阶乘2、Fibonacci数列3、Ackerman函数4、Hanoi塔问题优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。分治法的适用条件 分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。分治法的基本步骤 divide-and-conquer(P) { if ( | P | = n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }分治法的复杂性分析 分治法的算法应用 二分法搜索大整数的乘法Strassen矩阵乘法棋盘覆盖 合并排序与快速排序 线性时间选择最接近点对问题循环赛日程表第三章 动态规划动态规划基本思想 保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。动态规划算法的基本要素最优子结构性质 2、重叠子问题动态规划算法举例 完全加括号的矩阵连乘积最长公共子序列凸多边形最优三角剖分多边形游戏图像压缩流水作业调度0-1背包问题第四章 贪心算法贪心算法应用举例 活动安排问题 最优装载 哈夫曼编码 单源最短路径 最小生成树 多机调度问题第五章 回溯算法回溯法概念 具有限界函数的深度优先生成法称为回溯法。 回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。这种方法适用于解一些组合数相当大的问题。问题的解空间 1、问题的解向量、显约束、隐约束、解空间的概念 2、结点的状态：扩展结点、活结点、死结点回溯法的基本思想 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。回溯算法的结构 递归回溯与迭代回溯 两种典型的回溯问题：子集树与排列树回溯法的应用算法装载问题批处理作业调度符号三角形问题n后问题0-1背包问题 最大团问题 图的m着色问题 旅行售货员问题 圆排列问题 连续邮资问题 第六章 分支界限分支限界法应用单源最短路径问题 装载问题 布线问题 0－1背包问题 最大团问题 旅行售货员问题批处理作业调度分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分