2.3分片算法.ppt

1§ §3. 3. Divide-and-Conquer Divide-and-Conquer 第二章第二章(分片算法) (分片算法) 2 ---- 把问题分成若干子问题,先求得子问题的解,然后把这些解合并起来,得出母问题的解。若子问题的解是母问题的较小文本,从而可以递归地运算,那么这个算法往往就非常有效。 3§ § Divide-and-Conquer Divide-and-Conquer theory theory (分片算法原理) 4设计过程分为 3个阶段: ⑴Divide = 整个问题划分为多个子问题。⑵Conquer = 求解每个子问题(递归)。⑶ Combine = 合并子问题的解,形成原始问题的解。 1. -and-Conquer 算法的设计 5 例如, 例如, Merge-sort 算法: 问题问题分解子问题子问题子问题求解子 问题求解子 问题求解子 问题子问题解子问题解子问题解合并子问题解原问题 的解6分析过程: (当一个算法递归地调用自己时) ⑴.建立递归方程 T(n )⑵.求解 T(n )2. -and-Conquer 算法的分析 7递归方程的建立方法: 设输入大小为 n, T(n )为时间复杂性, 当n<c , T(n )=?(1) .Divide 阶段的时间复杂性: ?划分问题为 a个子问题。?每个子问题大小为 1/b 。⑴.Divide 划分时间可直接得到: D(n ) ⑵.Conquer 阶段的时间复杂性: aT(n/b ) ⑶.Combine 阶段的时间复杂性: C(n ) 8总之总之, , ?????????? C(n) (n) )b n aT( c n if )1()(D nT注: 求解递归方程 T(n )使用第一章介绍的方法。 9§ § 分片算法实例分片算法实例 10一、分片独立的情况--通过二分法分解或经过简单处理后,得到的是相似且相互独立的子问题