算法分治法PPT课件

2020/5/30，1，4章划分方法，4.1概述，4.2排序问题的划分方法，4.3组合问题的划分方法，4.4几何问题的划分方法，划分方法是最有名的算法设计技术。2020/5/30，2，4.1概述，4.1.1分区设计理念，4.1.2数字旋转矩形，2020/5/30，3，把难以直接解决的大问题分成小个子问题，分别解决子问题，结合子问题的解法。4.1.1分治法的设计思想如果子问题的规模还不够小，可以继续分解。2020/5/30，4，分割方法解决过程：分割-支配-和，(1)分割：将大小为n的原始问题分成大小较小的k个子问题，并使这个k子问题的大小尽可能相等。(2)子问题解决：每个子问题的解决方案通常与原始问题的解决方案相同，可以递归解决各个子问题。(3)结合：结合每个子问题的解决方案，分割算法的有效性在很大程度上取决于整合的实现。2020/5/30，5，2。独立子问题：每个子问题相互独立。1 .平衡子问题：最好使子问题的大小几乎相同。启发式规则：2020/5/30，6，分割法的一般情况，2020/5/30，7，范例：套用计算an，分割技术，以取得以下计算方法：并不是所有的分割方法都比简单的万有引力法有效。分析时间性能，2020/5/30，8，4.1.2数字旋转矩形，问题：输出nn (1n10)数字旋转矩形。2018171621323132313052333691423333332832526277891011，66的旋转矩形，2020/5/30，9，4.2排序问题的分割方式，4.2.1的排序顺序，4.2.2的快速排序，2020/5/30，10，4.3.1的排序顺序，双向合并排序的分割策略如下：(1)除以：要排序的序列R1、R2、rn具有相同长度的两个子序列R1，rn/2和rn/2 1、rn；(2)子问题解决：分别排序两个子序列，得到两个有序子序列。(3)合并(join):将这两个已排序的子序列合并为一个已排序的序列。2020/5/30，11，例如832667154，2020/5/30，12，2020/5/30，因为13，2-2-way集成阶段的时间复杂性为O(n)，所以2-way集成排序算法以以下递归方式存在：2路合并和排序的时间成本为O(nlog2n)。空间复杂性为O(n)，因为双向合并排序需要与合并过程中原始记录序列相同的存储空间量。2020/5/30，14，2020/5/30，15，4.3.2快速排序，(2)解决子问题：拆分后对每个子序列递归处理；(3)合并：子顺序R1.ri-1和ri 1rn.rn在当前位置内排序，因此无需执行合并。快速排序的分割策略如下：(1)分割：选取一个记录作为轴值，并将整个序列根据轴值分割为两个子序列。2020/5/30，16，合并排序根据序列中记录的位置划分序列，快速排序根据记录的值划分序列。2020/5/30，17，使用第一条记录作为轴值，分割排序顺序的过程(1)初始化：基于第一条记录，两个参数I，j；(2)右扫描过程：(3)左扫描过程：(4)重复步骤(2)(3)，直到I和j指向同一位置，即基准记录指向最终位置。2020/5/30，18，一次拆分示例，2020/5/30，19，2020/5/30，20，将要按轴值排序的系列分解为两个子系列，然后分别递归排序每个子系列。13、27、50、38、49、55、j、I、j、13、65、27、50、38、49，21，2020/5/30，22，T(n)=2t(n/2)n=2(2t(n/4)n/2)n=4t(n/4)2n=4(22.=nt (1) nlog2n=O(nlog2n)，因此时间复杂性为O(nlog2n)。最好将每次分割后要分割的部分分成长度相等的两个子序列。在具有n条记录的序列中，如果需要扫描一次要拆分的整个序列，则需要的时间为O(n)。如果将T(n)设置为对n条记录的序列进行排序的时间，则2020/5/30，23可用，因此时间复杂性为O(n2)。最坏的情况：要排序的记录序列的正数或相反顺序。此时需要n-1次迭代调用，第I次拆分必须通过n-i次键码比较，因此总比较次数为：2020/5/30，24，平均值：设置基准记录的键码k小于(1kn)是快速排序的平均时间性能，可以用归纳法证明，其个数也为O(nlog2n)。快速排序的空间复杂性是什么？2020/5/30，25，4.3组合问题的划分方法，4.3.1最大子段和问题，4.3.2板覆盖问题，补充：轮调度问题，2020/5/30，26，n指定由整数组成的序列(a1、a2、an)，最大子段和问题需要该序列的最大大小(1Ijn)。如果序列中的所有整数都是负整数，则其最大子区段和为0。例如，序列(-20，11，-4，13，-5，-2)的最大子区段和是：4.3.1最大子区段和问题，2020/5/30，27、最大子段和问题的分割策略如下：(1)分割：根据子问题平衡原则排序(a1、a2、an)作为等长的两个子序列(a1、a)和(a 1，an)除以，首先考虑最大子段和问题的简单算法2020/5/30，28， a1，an的最大子区段和=a1，a的最大子分段； a1，an的最大子段和=a 1，an的最大子段和； a1、an的最大子段和=，以及，(2)子问题解决：步骤划分的情况下和递归解决，情况需要分别计算，S1 S2是情况的最大子段和。(3)结合：在分割阶段的三种情况下，比较最大的子段和，将三种情况中的较大者作为原始问题的解决方案。2020/5/30，29，2020/5/30，30，2020/5/30，31，S1=0；lefts=0；/下一个匹配首先