2.3分片算法.ppt

1§ §3. 3. Divide-and-Conquer 第二章(分片算法) 2 ---- 把问题分成若干子问题,先求得子问题的解,然后把这些解合并起来,得出母问题的解。若子问题的解是母问题的较小文本,从而可以递归地运算,那么这个算法往往就非常有效。 3 §? Divide-and-Conquer ? theory ?(分片算法原理) 4 设计过程分为 3个阶段: ⑴ Divide = 整个问题划分为多个子问题。⑵ Conquer = 求解每个子问题(递归)。⑶ Combine = 合并子问题的解,形成原始问题的解。 -and-Conquer 算法的设计 5 例如, Merge-sort 算法: 问题问题分解子问题子问题子问题求解子 问题求解子 问题求解子 问题子问题解子问题解子问题解合并子问题解原问题 的解6 分析过程:(当一个算法递归地调用自己时) ⑴.建立递归方程 T(n) ⑵.求解 T(n) -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一、分片独立的情况--通过二分法分解或经过简单处理后,得到的是相似且相互独立的子问题