第六章 基本算法设计策略——分治法.ppt

VI、基本算法设计策略;基本策略;§6.1分治法 ; 从而，仅需3次乘法即可完成 ? 该算法即STARSSEN矩阵乘法的来源 ;极大极小;2．FFT;?该变换的逆变换为： 令 ，则上式可写为 ： 其它的一个重要性质：时域卷积对应于频域积。 ;多项式的积 两个多项式的积： 其中 此即卷积运算； ; 序列运算可用蝶形表示： 对于以下的8个的情形， 这一描述复杂并且不直观。 ;;这一变换基于运算中的性质： 从算法分析角度： 于是：分别考虑对其奇数项和偶数项作傅氏变换： 则 从而，可以将对N个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。 ; 实际计算时，注意到对另外一半 时： ;复杂度 ;应用：大数乘法 利用FFT计算积A=1634，B=9827 即 ; 对A与B进行逐一做积 进行反变换： 舍入成整数 ： 数表示成 ： ; 注意到可能的截断误差，使用数论变换更为适合 ;考虑在模F的域上的变换： 其中 ， 为在模F域上的逆。 一般取F：Mersenne数 或Fermat数 这样即可免去误差。 缺陷：无直接的物理意义。;数论变换;贪婪法;例：分数分解 ;算法：找到最接近的数 i=1 Label2: If p=1 then k(i)=q stop 1/k(i)=largest reciprocal less than p/q p/q=p/q-1/k(i) goto label2;;;显然，最优解为物品2和物品3：价值29 如果允许分数的，则可以找到最优解。 该问题是NP完全问题！;例：TSP;使用贪婪法，从A出发得到的最短路径：;;例：待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：;图示;说明;单源最短路径;1、算法基本思想;一个实例;计算复杂性： 对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。; 多机调度问题;一个实例;最小生成树性质;Prim算法;例：;算法改进;3、Kruskal算法;;说明