0a002算法分析与设计ss lecture2

第2（Divideand 1

算法2.1BinarySearch(Tlr l1;while rifT[m]=xthenreturn elseifT[m]>mthenrelse W(n)W )

2

Divide-and-if|P|cthendividePintoP1,P2,…,fori=1toyi=Divide-and-ReturnMerge(y1,y2,…,

W(|P1|)W(|P2|)...W(|Pk|)f4kf(n)

f(ni)

f(n)af

n)b

d第一类方程：迭代法、换递归树、尝试法5 T(n)aT(n/b)dT(n)O(nlogba)ad(n)=

O aT(n)

O(n)O(nlog

abaO(nlogba a例2.1测条件：有n片，(好至少比坏多1片). BA,B或A,B都命题2.1当n是偶数时，在上述规则下，经过一轮淘汰，剩下的好比坏至少多1片.与B都坏有k组，淘汰后，好数i，坏数k2i+2j+2k=2i+j>2k+ji>注：当n是奇数时，用其他测试轮空，如果轮空是好的，算法结束；否则淘汰轮空. n (3)

W(n)算法2.31．kwhilek>3将分成k/2组//轮空，特殊处fori=1tok/2if2then，则任取1else2k剩下的ifkthen任取2片测if1好1then取没测的else任取1片被测ifk 9 问题：设aa an an/2a na(n–1)/2a(n–1)/2 nW(n)=W(n/2)+(1)W(n)=(logn)FibonacciFibonacci1,1,2,3,5,8,13,21,Fn=Fn-1+Fn-增加F0=00,1,1,2,3,5,8,13,21,定理2.1{Fn}Fibonacci

n 1M1T(n(logn

M00例2.3设XYnn2k 令X＝A2n/2+B,Y=C2n/2XY=AC2n+(AD+BC)2n/2+BDW(n)=4W(n/2)+cn，W(1)=1W(n)=O(n2)代数变换ADBCA－BD－CACBDW(n)=3W(n/2)+cn，W(1)=1 A,B为两个n阶矩阵，n=2k,计算C=W(n分治法 A12 B12 C12

22 22 22W(n8W(n/2)W(1)= W(n)=

C12C22

Strassen M1=A11(B12－B22 W(n)7W(n)18(nM2=(A11+A12)B22M3=(A21+A22)M4=A22(B21－

M5=(A11+A22)(B11+B22 W(n)O(nlog27M6=(A12－A22)(B21+B22 O(n2.8075M7= B11+B12C11=M5+M4－M2+M6C12=M1+M2C21=M3+C22=M5+例2.5输入：集合S中有n个点，n>1，分治策略：子集PPLPR||||P2|||P2输入：n个点的集合P,X和Y分别为横、纵坐标数组在l右边MinDidtance(PL,XL,YLLPLMinDistance(PR,XR,YRRPR6．=min(L,Rd (/2)2

/ 2/442/2 252/365/检查1个点是常数时间，O(n)个点需要O(n)时间OT(n)2T

n)2

O(nlogT(n) n由递归树估计T(nW(n)T(n)O(nlog2T(n)2T(n)2T(n)

nW(n)=P12P1234X.21Y234XXYifp<thenqPartition(A,p,uicksortxijwhiletruerepeatjjuntilA[j]repeatiiuntilA[i]ifi<thenA[i]A[jj j

i 27 W(n)W(n1)nW(1)1W(n)

n(n1)Θ(n222 T(n)2T(n)n2

T(n)T(n)

T(9n)T(n) T(n)

Θ(nlognn1729Ln个不等的实数当为偶数时，中位数有2个，i=/2,

fori2tonifmaxthen5.return算法FindMaxMinW(n)=n/2+2n/22=n+n/22=3n/2复杂性：W(n)=n1+n2=2n 1．k ifkthenkk/2elsekifk>1thengotosecondmax命题2.2max在第一阶段的分组比较中总计进行了t/2k轮淘汰后只剩下一个元素max，利用t/2/2=n/2k=1.若n=2d，那么有k=d＝logn=logn若2d<n<2d＋1, W(n)=n1+logn1=n+logn找第k小的数 一，共nM=n/5个 S1S1C;ifk|S1|+1then输出elseifthenelserA B Dr2r2r3r27r

n |A=D= r 行2：O(n)行3：W(n/5)行4：O(n)行8-9W(7r

W(7r2)W(7(nW(7n3)W(7n

1)2ww(n)W(n)W(7n)cncn9cn81cn...5n 0.95 LL

0.812j

j

1的2n je

e

i

ω0

2 2 iω2e

ω3

ω4ei1,

e4i 22

22

ω6

i,

e

2 2 Ax