计算机算法基础(第二章).pptx

文档介绍：该【计算机算法基础(第二章) 】是由【wxq362】上传分享，文档一共【81】页，该文档可以免费在线阅读，需要了解更多关于【计算机算法基础(第二章) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2022/11/28
计算机算法基础
第一页,共八十一页。
2022/11/28
第二章分治法——“分”而治之

对大规模问题的求解
利用分治法求解大规模问题

在问题的输入规模很大时,无法直接求解,则采用将整个问题分成若干个小问题后分而治之。
一般情况下,子问题与原始问题“同质”
第二页,共八十一页。
2022/11/28

procedureDANDC(p,q)
(1:n);
integerm,p,q;//1≤p≤q≤n//
ifSMALL(p,q)
thenreturn(G(p,q))
else
m←DIVIDE(p,q)//p≤m<q//
return(COMBINE(DANDC(p,m),
DANDC(m+1,q)))
endif
endDANDC
注:
k=2:二分是最常用的分解策略;
SMALL(p,q):布尔函数,判断输入规模q-p+1是否足够小而无需再进一步分就可求解;
G(p,q):对输入规模为q-p+1的子问题求解(SMALL(p,q)为真时);
DIVIDE():对输入规模为q-p+1的子问题进一步分解,返回值为[p,q]区间进一步的分割点(SMALL(p,q)为真时;
COMBINE(x,y):子结果的合并函数,将区间[p,m]和[m+1,q]上的子问题的解合并成上级区间[p,q]上的“较完整”的解。当p=1,q=n时,就得到整个问题的解。

第三页,共八十一页。
2022/11/28
DANDC的计算时间
若所分成的两个子问题的输入规模大致相等,则DANDC总的计算时间可用递归关系式表示,如下:
g(n)n足够小
T(n)=
2T(n/2)+f(n)否则
注:
T(n):表示输入规模为n的DANDC计算时间
g(n):表示对足够小的输入规模直接求解的计算时间
f(n):表示COMBINE对两个子区间的子结果进行合并
的时间
(该公式针对具体问题有各种不同的变形)
第四页,共八十一页。
2022/11/28
(折半查找)

已知一个按非降次序排列的元素表a1,a2,…,an,判定某给定的元素x是否在该表中出现。
若是,则找出x在表中的位置并返回其所在下标
若非,则返回0值。
第五页,共八十一页。
2022/11/28
分治求解策略分析:
定义问题的形式描述:I=(n,a1,a2,…,an,x)
问题分解:选取下标k,由此将I分解为3个子问题:
I1=(k-1,a1,a2,…,ak-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,ak+2,…,an,x)
对于I2,若ak=x,则有解k,对I1、I3不用再求解;否则,
若x<ak,则只在I1中求解,对I3不用求解;
若x>ak,则只在I3中求解,对I1不用求解;
I1、I3上的求解可再次采用分治方法划分后求解(递归过程)
第六页,共八十一页。
2022/11/28


procedureBINSRCH(A,n,x,j)
integerlow,high,mid,j,n;
low←1;high←n;
whilelow≤highdo
mid←
case
x<A(mid):high←mid-1
x>A(mid):low←mid+1
else:j←mid;return
endcase
repeat
endNIBSRCH
注:
给定一个按非降次序排列的元素数组A(1:n),n≥1,判断x是否出现。
若是,置j,使得x=A(j)
若非,j=0
第七页,共八十一页。
2022/11/28
:设A(1:9)=(-15,-6,0,7,9,23,54,82,101)
在A中检索x=101,-14,82。执行轨迹见下表1
表1运行轨迹示例
x=101
x=-14
x=82
low
high
mid
low
high
mid
low
high
mid
1
9
5
1
9
5
1
9
5
6
9
7
1
4
2
6
9
7
8
9
8
1
1
1
8
9
8
9
9
9
2
1
找不到
找到
找到
成功的检索
不成功的检索
成功的检索
第八页,共八十一页。
2022/11/28

(A,n,x,j)能正确运行
证明:
1)在具体指定A中的数据元素及x的数据类型后,算法中的所有运算都
能按要求正确运行——即首先满足确定性和能行性
2)终止性
算法初始部分置low←1,high←n
①若n=0,不进入循环,j置0,算法终止
②否则,进入循环,计算mid,
或x=A(mid),j置为mid,算法终止;
或x<A(mid),置high←mid-1,搜索范围实际缩小为[low,mid-1],
进入下次循环,对[mid+1,high]区间不做进一步搜索;
或x>A(mid),置low←mid+1,进入下次循环;搜索范围实际缩小
为[mid+1,high],对[low,mid-1]区间不做进一步搜索;
因low,high,mid都是整型变量,故按照上述规则,在有限步内,或找到某个mid,有A(mid)=x;或变得low>high,在A中没有找到任何元素等于x,算法终止。
第九页,共八十一页。
2022/11/28

1)空间特性
n+5个空间位置——О(n)
2)时间特性
区分以下情况,并进行相应的分析
成功检索:所检索的x出现在A中。
成功检索情况共有n种:x恰好是A中的某个元素,A中共有n个元素,故有n种可能的情况
不成功检索:所检索的x不出现在A中。
不成功检索情况共有n+1种:x<A(1),或A(i)<x<A(i+1),1≤i<n-1或x>A(n)
成功/不成功检索的最好情况:执行步数最少,计算时间最短
成功/不成功检索的最坏情况:执行步数最多,计算时间最长
成功/不成功检索的平均情况:一般情况下的计算时间
第十页,共八十一页。