当前位置:首页 >> 学科竞赛 >> 9分治算法

9分治算法


递归与分治策略

授课:陈嘉庆

分治策略
● 任何一个可以用计算机求解的问题所 需的计算时间都与其规模有关。问题规模 越小,解题所需的计算时间往往也越少, 从而也越容易计算。想解决一个较大的问 题,有时是相当困难的。分治法的思想就 是,将一个难以直接解决的大问题,分割 成一些规模较小的相同问题,以便各个击 破,分而治之。

/>
分治策略
● 分治法:有很多算法在结构上是递归的:为了 解决一个给定的问题,算法要一次或多次地调用 其本身来解决相关的子问题。这些算法通常采用 分治策略:将原问题分成n个规模较小而结构与原 问题相似的子问题。递归地解这些子问题,然后 合并结果就得到原问题的解。n=2时的分治法又 称二分法。 ● 分治的基本思想是将一个规模为n的问题分解 为k个规模较小的子问题,这些子问题互相独立且 与原问题相同。找出各部分的解,然后把各部分 的解组合成整个问题的解。

算法总体思想
● 将要求解的较大规模的问题分割成k个更小规模的子问 题。

T(n)

=

n

T(n/2)

T(n/2)

T(n/2)

T(n/2)

算法总体思想
● 对这k个子问题分别求解。如果子问题的规模仍然不够 小,则再划分为k个子问题,如此递归的进行下去,直 到问题规模足够小,很容易求出其解为止。

T(n)
n/2

=
n/2

n
n/2 n/2

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4

算法总体思想
● 将求出的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。

T(n)
n/2

=
n/2

n
n/2 n/2

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4

分治算法
● 1、解决算法实现的同时,需要估算算 法实现所需时间。分治算法时间是这样确 定的: 解决子问题所需的工作总量(由 子问 题的个数、解决每个子问题的工作量 决定) 合并所有子问题所需的工作量 ● 2、分治法是把任意大小问题尽可能地 等分成两个子问题的递归算法

递归算法要点
● 设定边界条件 ● 一般使解决的问题规模变小 ● 自身调用。

分治的具体过程
● begin {开始} if ①问题不可分 then ②返回问题解 else begin
③从原问题中划出含一半运算对象的子问题1; ④递归调用分治法过程,求出解1; ⑤从原问题中划出含另一半运算对象的子问题2; ⑥递归调用分治法过程,求出解2; ⑦将解1、解2组合成整修问题的解;

end; end; {结束}

【例1】归并排序
● 【例1】归并排序(合并排序),将序列 A[1],A[2],A[3]…A[N]进行归并排序。 ● 归并排序也是基于分治策略的另一 个算法。归并的思路是把两个已经排好序 的数组合并为一个。
初始值 一趟归并排 序
E Y U K S L B E Y K U L S B

两趟归并排 序
三趟归并排 序

E

K

U

Y

B

L

S

B

E

K

L

S

U

Y

合并排序
算法mergeSort的递归过程可以消去。
初始序列

[49] [38] [65] [97] [76] [13] [27]

第一步

[38 49]

[65 97]

[13 76]

[27]

第二步

[38 49 65 97]

[13 27 76]

第三步

[13 27 38 49 65

76 97]

分治基本步骤
基本思想:将待排序元素分成大小大致相同的2个子集合,分 别对2个子集合进行排序,最终将排好序的子集合合并成为所 要求的排好序的集合。

if 问题不可分 then 求解 else (1)分出问题的一个子问题1, 并求解子问题1 (2)分出问题的一个子问题2, 求解子问题2 (3)合并子问题1和子问题2

if p=r then 结束(只有一个元素,默认排序好) else merge_sort(A,p,q);

Merge_sort(A,q+1,r);
merge(A, p,q,r);

合并排序算法分析
● 【算法分析】:合并排序的算法就是二分法。 ● 【分解】:将n个元素各含或个元素的子序列; ● 【合并】:合并两个已排序的子序列以得到排序结果。 ● 在对子序列排序时,当其长度为1时递归结束,单个 元素被视为是已排序的关键步骤在于合并步骤中产生的两 个已排好序的子序列将它们合并为一个已排好序的子序列。 我们引入一个辅助过程merge(A,P,Q,R)来完成这一合并 工作,其中A是数组,P,Q,R是下标。这个过程如果用玩 扑克来比喻,同学们可以更容易理解:桌面上有两堆牌, 每一堆都是排好序的,最小的牌在最上面,我们希望把这 两碓牌合并成排好序的一堆加以输出,基本步骤包括:先 取面朝上的两堆牌的顶上两张中较小的一张,将它取出面 朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。 这时把另一个输入堆中余下的牌面朝下放入即可。

合并排序
?最坏时间复杂度:O(nlogn) ?平均时间复杂度:O(nlogn) ?辅助空间:O(n) ?稳定性:稳定
●解决算法实现的同时,需要估算算法实现所需时间。分治 算法时间是这样确定的: 解决子问题所需的工作总量(由 子问题的个数、解决 每个子问题的工作量 决定) 合并所有子问题所需的工作量

【例2】快速排序
● ● 快速排序是基于分治策略的一个排序算法。按 照分治法的思想分析快速排序: (1)【分解】(Divide) 以元素a[p]为基准元素将a[p:q-1]划分为三段 a[p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何一个元 素都小于a[q],a[q+1:r]中任何一个元素大于等于a[q],下 标q在划分中确定。 (2)【递归求解】(Conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和 a[q+1:r]进行排序。 (3)【合并】(Merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进 行的,所以不必进行任何合并操作就已经排好序了。 在上面三个步骤中,第一步:分解是关键,一 次快速排序确定划分元素的位置。

● ● ●

● procedure qsort(l,r:integer); ● var i,j,mid:integer; ● begin ● i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} ● repeat ● while a[i]<mid do inc(i); {在左半部分寻找比中间数大的数} ● while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数} ● if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} ● swap(a[i],a[j]); ● inc(i);dec(j); {继续找} ● end; ● until i>j; ● if l<j then qsort(l,j); {若未到两个数的边界,则递归搜索左右区间} ● if i<r then qsort(i,r); ● end;{sort}

二分搜索技术
给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找 出一特定元素x。 ? 分析: 该问题的规模缩小到一定的程度就可以容易地解决; ? 该问题可以分解为若干个规模较小的相同问题; ? 分解出的子问题的解可以合并为原问题的解; ? 分解出的各个子问题是相互独立的。 分析:如果n=1即只有一个元素,则只要比较这个元素和x就 分析:比较x和a的中间元素a[mid],若x=a[mid],则x在L中的 可以确定x是否在表中。因此这个问题满足分治法的第一个适 位置就是mid;如果x<a[mid],由于a是递增排序的,因此假 分析:很显然此问题分解出的子问题相互独立,即在a[i]的前 用条件 如x在a中的话,x必然排在a[mid]的前面,所以我们只要在 面或后面查找x是独立的子问题,因此满足分治法的第四个适 a[mid]的前面查找x即可;如果x>a[i],同理我们只要在a[mid] 用条件。 的后面查找x即可。无论是在前面还是后面查找x,其方法都 和在a中查找x一样,只不过是查找的规模缩小了。这就说明 了此问题满足分治法的第二个和第三个适用条件。

二分搜索技术
给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找 出一特定元素x。 算法复杂度分析: 据此容易设计出二分搜索算法:
// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x // 找到x时返回其在数组中的位置,否则返回-1 int left = 0; int right = n - 1; while (left <= right) int middle = (left + right)/2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; return -1; // 未找到x

每执行一次算法的 while循环, 待搜索数 组的大小减少一半。因 此,在最坏情况下, while循环被执行了 O(logn) 次。循环体内 运算需要O(1) 时间, 因此整个算法在最坏情 况下的计算时间复杂性 为O(logn) 。

分治法的适用条件
分治法所能解决的问题一般具有以下几个特征: ● 该问题的规模缩小到一定的程度就可以容易地解决; ● 该问题可以分解为若干个规模较小的相同问题,即该 问题具有最优子结构性质 ● 利用该问题分解出的子问题的解可以合并为该问题的 解; ● 该问题所分解出的各个子问题是相互独立的,即子问 题之间不包含公共的子问题。 这条特征涉及到分治法的效率,如果各子问题是不 能否利用分治法完全取决于问题是否具有这条特征, 这条特征是应用分治法的前提,它也是大多数问题 因为问题的计算复杂性一般是随着问题规模的增加 可以满足的,此特征反映了递归思想的应用 而增加,因此大部分问题满足这个特征。 独立的,则分治法要做许多不必要的工作,重复地 如果具备了前两条特征,而不具备第三条特征,则 可以考虑贪心算法或动态规划。 解公共的子问题,此时虽然也可用分治法,但一般 用动态规划较好。

【例题分析】
● 【比赛安排】 ● 设有2^n(n<=6)个球队进行单 循环比赛,计划在2^n-1天内完 成,每个队每天进行一场比赛。 设计一个比赛的安排,使在 2^n-1天内每个队都与不同的 对手比赛。

n=2时的比赛安排为:
1 2 3 4

2

1

4

3

3

4

1

2

4

3

2

1

n=4时的比赛安排为:

n=8时的比赛安排为:

1

2

3

4

1 2

2 1 4 3 6 5 8 7

3 4 1 2 7 8 5 6

4 3 2 1 8 7 6 5

5 6 7 8 1 2 3 4

6 5 8 7 2 1 4 3

7 8 5 6 3 4 1 2

8 7 6 5 4 3 2 1

2

1

4

3
3

3

4

1

2

4 5 6 7 8

4

3

2

1

剔除多余括号(CTSC94-1)
● 键盘输入一个含有括号的四则运算表达式,可能含有多余的括号, 编程整理该表达式,去掉所有多余的括号,原表达式中所有变量 和运算符相对位置保持不变,并保持与原表达式等价。 ● 例如:
输入表达式 应输出表达式 A+b(+c) A+b+c

(a*b)+c/(d*e)
A+b/(c-d)

A*b+a/(d*e)
A+b/(c-d)

注意输入a+b时不能输出b+a。 表达式以字符串输入,长度不超过255,输入不需要判错。 所有变量为单个小写字母。只是要求去掉所有多余括号,不要求对表达式简化。

分析:
● ● ● ● 对于四则运算表达式,我们分析一下哪些括号 可以去掉。 设待整理的表达式为(s1 op s2);op为括号内 优先级最低的运算符(“+”,“-”或“*”, “/”); 左邻括号的运算符为“/”,则括号必须保留, 即…/(s1 op s2)…形式。 左邻括号的预算符为“*”或“-”。而op为“+” 或“-”,则保留括号,即…*(s1+s2)…或…(s1+s2)…或…*(s1-s2)…或…-(s1s2)…。 右邻括号的运算符为“*”或“/”,而op为“+” 或“-”,原式中的op运算必须优先进行,因此括 号不去除,即(s1+s2)*… 除上述情况外,可以括号去除,即…s1 op s2… 等价于…(s1 op s2)… 我们从最里层嵌套的括号开始,依据上述规律 逐步向外进行括号整理,直至最外层的括号保 留或去除为止。这个整理过程可以用一个递归 过程来实现。图26 括号剔除示例图 例如,剔除表达式“((a+b)*f)-(i/j)”中 多余的括号。依据上述算法进行整理的过程如 图。
图26 括号剔除示例图

● ● ●




更多相关文档:

分治算法

《算法设计与分析》实验报告 实验 1 一、实验目的 1、掌握分治算法的设计思想...{3,25,34,1,99,64,33,9,32,7,13,12,43,3,6,99,88,66,56,41}; ...

分治算法试题

分治算法试题_理学_高等教育_教育专区。分治算法当我们求解某些问题时,由于这些...例如有下面一组元素: -13,13,9,-5,7,23,0,15。用分治策略比较的过程如...

分治算法实验报告

一、实验目的 1.加深对分治算法的基本思想、 基本步骤和一般形式的理解, 掌握...9 9 6 10 4 4 5 5 0 9 10 10 12 12 13 0 0 17 18 18 12 11 ...

算法分析——分治法

第 9 页 依据分治法设计程序时的思维过程………第………九、分治法与其它常见算法的比较………第 9 页 分治法与其它常见算法的比较………第……… 小组的分...

算法设计 第4章 分治法

算法设计 第4章 分治法_计算机软件及应用_IT/计算机_专业资料。算法设计 清华大学...{ 6, 7, 8, 9,10}, {11,12,13,14,15}, {16,17,18,19,20}, {...

实验三 分治算法设计与应用

实验三 分治算法设计与应用一.实验目的和要求 1.加深对分治算法的基本思想、 ...9 9 6 10 4 4 5 5 0 9 10 10 12 12 13 0 0 17 18 18 12 11 ...

分治算法实验报告

9页 1下载券 分治算法 5页 免费 分治算法 51页 1下载券 第四章分治算法 19...问题的分治算法实验 二分搜索问题的分治算法实验 二分搜索问题的分治 指导教师及...

算法设计与分析 分治算法基本思想

算法设计与分析 分治算法基本思想_IT/计算机_专业资料。算法设计与分析 ...以下是 n=9 的二元比较树: 5 2 7 1 3 6 8 n=9 情况下折半搜索的...

实验2 分治法算法设计

实验2 分治算法设计_计算机软件及应用_IT/计算机_专业资料。算法分析与设计,实验...每次增 10000 9 n ( 10000 次) srch 50000 60000 70000 8000 90000 100000...

贪心算法、分治算法、动态规划算法间的比较.doc

贪心算法、分治算法、动态规划算法间的比较.doc_电脑基础知识_IT/计算机_专业资料...图1 图2 贪心算法解题过程:自顶向下从第一层 9 开始,到第二层,选数值较 ...
更多相关标签:
分治算法 | 分治算法求最大最小值 | 多项式乘积的分治算法 | 分治算法经典例题 | 分治算法 最邻近点对 | 分治算法时间复杂度 | 分治算法的时间复杂度 | 分治排序算法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com