22问题复杂度1.docx
- 文档编号:14304807
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:23
- 大小:1MB
22问题复杂度1.docx
《22问题复杂度1.docx》由会员分享,可在线阅读,更多相关《22问题复杂度1.docx(23页珍藏版)》请在冰点文库上搜索。
22问题复杂度1
选择算法的时间复杂度分析
下界证明方法:
构造最坏输入
•任意给定一个算法A,A对于任意输入x都存在一个确定的操作序列τ
•τ中的操作分成两类:
–决定性的:
能够对确定输出结果提供有效信息
–非决定性的:
对确定结果没有帮助的冗余操作
•根据算法A构造某个输入实例x,使得A对x的操作序列τ包含尽量多的非决定性操作.
•给出冗余操作+必要的操作的计数公式
1
选择算法的有关结果
算法最坏情况空间选最大顺序比较n-1O
(1)
选最大顺序比较2n-3O
(1)
和最小算法
FindMaxMin
⎡3n/2⎤-2O
(1)
选第二大顺序比较2n-3O
(1)
锦标赛方法n+⎡logn⎤-2O(n)
选中位数排序后选择O(nlogn)O(logn)
算法SelectO(n)~2.95nO(logn)
选最大算法Findmax是最优的算法
2
选最大与最小算法
定理6任何通过比较找最大和最小的算法至少需要⎡3n/2⎤-
2次比较.
证明思路:
任给算法A,根据算法A的比较结果构造输入
T,使得A对T至少做⎡3n/2⎤-2次比较.
证:
不妨设n个数彼此不等,A为任意找最大和最小的算法.max是最大,A必须确定有n-1个数比max小,通过与max
的比较被淘汰.min是最小,A也必须确定有n-1个数比
min大,通过与min的比较而淘汰.总共需要2n-2个信息单位.
3
基本运算与信息单位
数的状态标记及其含义:
N:
没有参加过比较W:
赢
L:
输WL:
赢过且至少输1次
如果比较后数的状态改变,则提供信息单位,状态不变不提供信息单位,每增加1个W提供1个信息单位每增加1个L提供1个信息单位.
两个变量通过一次比较增加的信息单位个数不同:
0,1,2case1:
N,N→W,L:
增加2个信息单位
case2:
W,N→W,L:
增加1个信息单位case3:
W,L→W,L:
增加0个信息单位
4
算法输出与信息单位
算法输出的条件:
n-2个数带有W和L标记,最大数只带W标记,最小数只带
L标记,总计2n-2个信息单位
对于任意给定的算法,构造输入的原则是:
根据算法的比较次序,针对每一步参与比较的两个变量的状态,调整对参与比较的两个变量的赋值,使得每次比较后得到的信息单位数达到最小.从而使得为得到输出所需要的2n-2个信息单位,该算法对所构造的输入至少要做⎡3n/2⎤-2次比较.
5
对输入变量的赋值原则
W,N;WL,Nx>yW,L;WL,L1
一个赋值的实例
x1,x2---x1>x2;x1,x5---x1>x5;x3,x4---x3>x4;x3,x6---x3>x6
x3,x1---x3>x1;x2,x4---x2>x4;x5,x6---x5>x6;x6,x4---x6>x4…
x1
x2
x3
x4
x5
x6
状态
值
状态
值
状态
值
状态
值
状态
值
状态
值
N*
N*
N*
N*
N*
N*
x1>x2
W
20
L
10
x1>x5
W
20
L
5
x3>x4
W
15
L
8
x3>x6
W
15
L
12
x3>x1
WL20
W
25
x2>x4
WL10
L
8
x5>x6
WL
5
L
3
x6>x4
L
2
WL
3
构造的输入为(20,10,25,2,5,3)7
问题复杂度的下界
为得到2n-2个信息单位,对上述输入A至少做⎡3n/2⎤-2次比较.
一次比较得到2个信息单位只有case1.A至多有⎣n/2⎦个
case1,至多得到2⎣n/2⎦≤n个信息单位.其它case,1次比较至多获得1个信息单位,至少还需要n-2次比较.
当n为偶数,A做的比较次数至少为
⎣n/2⎦+n-2=3n/2-2=⎡3n/2⎤-2
当n为奇数,A做的比较次数至少为
⎣n/2⎦+n-2+1=(n-1)/2+1+n-2=⎡3n/2⎤-2
结论:
FindMaxMin是最优算法
8
找第二大问题
元素x的权:
w(x),表示以x为根的子树中的结点数初始,w(xi)=1,i=1,2,…,n;
赋值原则:
在比较的时候进行赋值或者调整赋值.只对没有
失败过的元素(权大于0的元素)进行赋值.来胜的次数多的仍旧胜,输入值也大.
权大者胜,原
1.w(x),w(y)>0:
若w(x)>w(y),那么x的值大于y的值;//权大者胜
w(x)=w(y),xy;//,
2.w(x)=w(y)=0,那么x,y值不变;//x与y比较对于确定第二大无意义
9
实例
w(x1)
w(x2)
w(x3)
w(x4)
w(x5)
值
初始
1
1
1
1
1
*,*,*,*,*
第1步
x1>x2
2
0
1
1
1
20,10,*,*,*
第2步
x1>x3
3
0
0
1
1
20,10,15,*,*
第3步
x5>x4
3
0
0
0
2
20,10,15,30,40
第4步
x1>x5
5
0
0
0
0
41,10,15,30,40
构造树
根据算法A的比较次序,在比最大的过程中如下构造树:
1.初始是森林,含有n个结点;
2.如果x,y是子树的树根,则算法比较x,y;
3.若x,y以前没有参加过比较,任意赋值给x,y,比如x>y;那么将y作为x的儿子;
4.若x,y已经在前面的比较中赋过值,且x>y,那么把y作为x的儿子,以y为根的子树作为x的子树;
11
x1>x2
x1>x3
x5>x4
x1
x2x1
x2x3
x1
x
x4x5
x5
实
x23x4
x1例
x1>x5
x2x3x5
x412
找第二大问题复杂度下界
针对这个输入,估计与max比较而淘汰的元素数根的权为n,其它的结点权为0,根为max
wk表示max在它第k次比较后形成以max为根子树的结点总数,则wk≤2wk-1,设K为max最终与权不为0的结点的比较次数,则
n=wK
≤2Kw0
≤2K
⇒K≥
logn⇒K
≥⎡logn⎤
这K个元素彼此不同,因为同一个元素不可能被计数2次.其中为确定第二大,要淘汰K-1个元素,至少用⎡logn⎤-1次比较.
结论:
锦标赛方法是找第二大的最优算法.
13
找中位数问题
定理8设n为奇数,任何通过比较运算找n个数的中位数
(median)的算法在最坏情况下至少做3n/2-3/2次比较
证首先定义决定性的比较与非决定性的比较.决定性的比较:
建立了x与median的关系的比较.
∃y(x>y且y≥median),x满足上述条件的第一次比较
∃y(x (比较时y与median的关系可以不知道) 非决定性的比较: 当x>median,y 为找到中位数,必须要做n-1次决定性的比较. 针对算法构造输入,使得非决定性比较达到(n-1)/2次. 14 输入构造方法 1.分配一个值给中位数median; 2.如果A比较x与y,且x与y没有被赋值,那么赋值x,y使得 x>median,y 3.如果A比较x与y,且x>median,y没被赋值,则赋值y使得 y 4.如果A比较x与y,且x y>median; 5.如果存在(n-1)/2个元素已得到小于median的值,则对未赋值的全部分配大于median的值; 6.如果存在(n-1)/2个元素已得到大于median的值,则对未赋值的全部分配小于median的值. 7.如果剩下1个元素则分配median给它. 15 构造实例 x1,x2---x1>x2;x3,x4---x3>x4;x5,x6---x5>x6; x1,x3---x1>x3;x3,x7---x3>x7;x7,x4---x7>x4;… 1.初始median=4 非决定性比较 决定性比较 16 复杂性分析 元素状态N: 未分配值;S: 得到小于median值; L: 得到大于median值 这样赋值的输入使得A在这个输入下所进行的上述比较都是非决定性的.这样的比较至少有(n-1)/2个.因此总比较次数至少为 (n-1)+(n-1)/2=3n/2-3/2 结论: Select算法在阶上达到最优. 17 几种选择算法的总结 问题 算法 最坏情况 问题下界 最优性 找最大 Findmax n-1 n-1 最优 找最大最小 FindMaxMin ⎡3n/2⎤-2 ⎡3n/2⎤-2 最优 找第二大 锦标赛 n+⎡logn⎤-2 n+⎡logn⎤-2 最优 找中位数 Select O(n) 3n/2-3/2 阶最优 找第k小 Select O(n) n+min 阶最优 {k,n-k+1}-2 问题P,问题Q 通过归约确认问题计算复杂度的下界 问题Q的复杂度已知(至少线性)∧(g(n)) 存在变换f将Q的任何实例转换成P的实例,f的时间为线性时间f(n)=O(n),解的反变换s(n)也是线性时间 解Q的算法: TQ(n)=f(n)+Tp(n)+s(n) 1.将Q的实例I变成f(I),f(n) 2.用解P的算法作为子程序解f(I),时间与解P的时间为同样的阶Tp(n) 3.将解变换成原问题的解s(n) 解P的算法可以解Q.且时间的阶一样,因此P至少与Q一样难.Q≤lP(l表示线性时间) f(n)+Tp(n)+s(n)=TQ(n)=(g(n)) 19 •问题: 因子分解与素数测试 因子分解factor: 输入正整数n,factor(n)是多重集 (全部素因子)规定factor (1)={1} 素数测试testp: 输入正整数n,test(n)为“Yes”或者“No” •归约: testp≤factor 假设testp问题的难度是W(n). 素数测试算法A(n) 1.ifn=1thenreturn“No” 2.elsep←factor(n) 3.if|p|≥2thenreturn“No” 4.elsereturn“Yes” •结论: ∧(W(n))=Ttestp(n)≤Tfactor(n) 20 元素唯一性问题 •问题: 给定n个数的集合S,判断S中的元素是否存在相同元素. •元素唯一性问题的复杂度为Θ(nlogn) 输入: 多重集S={n1⋅a1,n2⋅a2,…,nk⋅ak} 构造决策树,树叶为S的全排列数 n! 最坏情况下树深为 n1! n2! ... nk! Θ(logn! )Θ(nlogn) 21 最邻近点对与唯一性问题 •P问题与Q问题: P: 平面直角坐标系中n个点的最邻近点对问题Close Q: 元素的唯一性问题Uniqueness∧(nlogn) •变换f: Q的实例: x1,x2,…,xn,变成点(x1,0),(x2,0),…,(xn,0) •解Q算法: 1.利用求最邻近点对算法P计算最短距离d 2.ifd=0thenreturn“No” 3.elsereturn“Yes” •结论: 计算平面直角坐标系中n个点的最邻近点对问题的时间是∧(nlogn),其中算法以比较为基本运算 22 最小生成树与唯一性问题 •P问题与Q问题: P: 平面直角坐标系中n个点的最小生成树问题; Q: 元素的唯一性问题Uniqueness∧(nlogn) •变换f: Q的实例: x1,x2,…,xn,变成X轴上的n个点, •解Q算法: 1.利用求最小生成树算法P构造树T,确定T的最短边e. 2.检测e的长度是否为0 3.if|e|=0then不唯一,else是唯一的. •结论: 计算平面直角坐标系n点最小生成树时间是 ∧(nlogn),其中算法以比较为基本运算 23
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 22 问题 复杂度