科大算法导论上课ppt完整版_算法导论ppt资源-CSDN文库

共14个文件

ppt：13个

pdf：1个

需积分: 9 21 浏览量 2018-12-21 22:36:36 上传评论 4 收藏 5.66MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

package

算法导论ppt完整版.zip （14个子文件）

第八次课_20161114111415999.ppt 192KB

第七次课_20161177475617.ppt 167KB

第三次课_201693017141576(1).ppt 245KB

第九次课_20161118171831660.ppt 118KB

第六次课_2016103181714721.ppt 80KB

第二次课_201692674030870(1).ppt 478KB

第四－五次课_2016102475217168(1).ppt 141KB

算法分析 2-14章(1).pdf 5.2MB

第十四次课_201612268150501.ppt 89KB

第十次课_20161125155030593.ppt 63KB

第十二次课_2016121273826414.ppt 122KB

第一次课_201692674012978(1).ppt 225KB

第十三次课_201612197422803(1).ppt 122KB

第十一次课_201612573146711.ppt 110KB

第三章分治法及递归算法的分析方法

3.1 分治法(Divide-and-conquer)

1. 什么是分治法

当求解的问题较复杂或规模较大时，不能立刻得到

原问题的解，但这些问题本身具有这样的特点，它

可以分解为若干个与原问题性质相类似的子问题，

而这些子问题较简单可方便得到它们的解，因此通

过合并这些子问题的解就可得到原问题的解。

2. 应用分治法的三个基本步骤

①分解问题(divide)：把原问题分解为若干个与原问题

性质相类似的子问题

②求解子问题(conquer)：不断分解子问题直到可方便

求出子问题的解为止

③合并子问题的解(combine)：合并子问题的解得到原

问题的解

3. 归并排序(Merge Sort)

思想：如果能把原待排序的数组分解成若干个待排序的

子数组，而这些子数组可以方便地排好序，并且通过

合并这些子数组的解将能得到原问题的解，则整个数

组将排好序。

应用分治法解题的三个基本步骤为：

①divide ：把具有n个元素的数组分解为二个n/2大小的

子数组

②conquer：递归地分解子数组，直到子数组只包含一

个元素为止

③combi ne：二二合并已排好序的子数组使之成为一个

新的排好序的子数组，重复这样二二合并的过程直到

得到原问题的解

由分治法三个步骤可方便得到解此问题的算法：

Merge-sort(A,p,r)

if p<r

then q└(p+r)/2┘

Merge-sort(A,p,q)

Merge-sort(A,q+1,r)

Merge(A,p,q,r)

Merge(A,p,q,r) 执行次数

n

1

q-p+1 1

n

2

r-q 1

for i1 to n

1

n

1

+1≤n+1

do L[i]A[p+i-1] n

1

≤n

for j1 to n

2

n

2

+1≤n+1

do R[j]A[q+j] n

2

≤n

L[n

1

+1]∞ 1

R[n

2

+1]∞ 1

i1 1

j1 1

for kp to r r-p+2≤n+1

do if L[i]≤R[j] r-p+1≤n

then A[k]L[i] ≤n

1

ii+1 ≤n

1

else A[k]R[j] ≤n

2

jj+1 ≤n

2

内容反馈

兔兔老爹

粉丝: 2
资源: 9

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip