分治法的应用

2 2,1 ?合并排序输入规模:元素个数 n基本操作:比较效率类别: While (i<p)and(j<q) 循环次数与 i、j有关。最佳情况——每次循环 i或j之一增加,很快达到上限,结束循环。待排序元素已排序, B、C署组织以很快完成合并。最坏情况——每次循环两变量交替增加,循环次数很多。较小元素轮流来自两个数组。时间复杂度为: 1 log )(???nnnnT - 6- 分治法的应用?快速排序输入规模:元素个数 n基本操作:比较效率类别:每次分裂点位置不同,所得两个子分区大小就不同,即子排序问题规模不同,因此,快速排序有最佳、最差、平均效率。最佳效率:每次分裂都再区域中点,将区域一分为二,得大小相同的两个子区域。左右扫描指针交叉时满足 i=j ,比较总次数 n。????????nnnnfnT nnT k log 2 ),()2/(2 1,0)( 最差效率:每次分裂都在区域两端,两子区域其一为空,另一个只比原来区域少一个元素——输入序列已排序。总比较次数——不包含判断左右指针交叉的那 1次比较。 12/)1(112.... )1()(??????????nnnnnT 平均时间效率:大小为 n的随机排列数组,平均比较次数记为)(nT avg 设分列颠 s位于每个位置的概率相同为 1/n 。两子区的平均比较次数之和为)1()(snTsT avg avg???。nnnnnsnTsTnnT ns avg avg avg log 38 .1 ln2)1( )]1()([/1)( 10???????????3 程序运行平台 VC++6.0 - 7- 分治法的应用 4 总体设计原问题 S子问题 Sk 子问题 S1 S1的解Sk的解 S的解子问题 S2 S2的解…………. ……………图 4.1 分治法的设计思想分治法的应用查找问题合并排序问题快速排序问题图 4.2 分治法应用的总体设计