分治法的基本框架 Divide-and-Conquer(P) if(|P|≤c) return( Solve(P)) else Partition(P)→P1P2……Pk for( int i=1; k<=k; ++1) yi= Divide-and-Conquer(Pi) Merge(y1,y2……….yk) return 11
11 分治法的基本框架 Divide-and-Conquer ( P ) { if ( |P| < c ) return ( Solve (P) ) else { Partition ( P ) → P1 , P2 ……Pk for ( int i=1; i<=k; ++I ) yi = Divide-and-Conquer ( Pi ) Merge ( y1 , y2…… yk ) return } }
2
12
顺序检索性能分析 今检索成功 假设检索每个关键码是等概率的:P1=1/n ∑Pi·(n-i)=-∑( 0 10 n+ ☆检索失败 设检素失败时都需要比较n+1次(设置了一个监 视哨) 13
13 顺序检索性能分析 ❖ 检索成功 假设检索每个关键码是等概率的：Pi = 1/n ❖ 检索失败 假设检索失败时都需要比较n+1次（设置了一个监 视哨） Pi n i i n n n i i n i n i n ·( − ) ( ) = − = − = − = = + = 0 1 1 0 1 1 2 1
顺序检索平均检索长度 令假设检索成功的概率为,检索失败的概率为 q=(1p) n+1 △SL=P2 +q·(n+1) n+1 P·~+(1-p)(n+1) =(n+1)(1-P/2) s(n+1)/2<ASL<(n+1) 14
14 顺序检索平均检索长度 ❖ 假设检索成功的概率为p，检索失败的概率为 q=(1-p) （n+1)/2 < ASL < (n+1) 1 ASL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p q n n p p n n p + = + + + = + − + = + −
顺序检索优缺点 令优点:插入元素可以直接加在表尾 e(1) 缺点:检索时间太长(mn) 15
15 顺序检索优缺点 ❖优点：插入元素可以直接加在表尾 Θ(1) ❖缺点：检索时间太长Θ(n)