第三章 分治算法习题 1、编写程序实现归并算法和快速排序算法 参见后附程序 2、用长为100、200、300、400、500、600、700、800、900、1000 的10 个数组的排列来统计这两种算法的时间复杂性。 有些同学用的微秒us 用s 可能需要把上面的长度改为10000，……，100000，都可以 大部分的结果是快速排序算法要比归并算法快一些。 3、讨论归并排序算法的空间复杂性。 解析：归并排序由分解与合并两部分组成，如果用( )S n 表示归并排序所用的空间。 则由 MergeSort(low, mid) //将第一子数组排序 )2/(nS MergeSort(mid+1, high) //将第二子数组排序 )2/(nS Merge(low, mid, high) //归并两个已经排序的子数组 nnO2)( 则 )}(),2/(max{)(nOnSnS )()2/()(nOnSnS 递归推导得 )()2()1()()2()2()2()1()()2()4()()2()(1nOnOSnOnOnOnOSnOnOnSnOnSnSkk 又由存储数组长度为n ，则有 )()(nOnS 因此，空间复杂度为)(nO。 4、说明算法PartSelect 的时间复杂性为( )O n 证明： （1）当7r 时，假设数组A 中元素互不相同。由于每个具有7 个元素的数组的中间值 u是该数组中的第4 小元素，因此数组中至少有4 个元素不大于 u，/ 7n 个中间值中至少有/ 7 / 2n 个不大于这些中间值的中间值 v。因此，在数组A 中至少有 4/ 7 / 22/ 7nn 个元素不大于v 。换句话说，A 中至多有 5122/ 72( / 7/ 7),(06)77nnnnene 个元素大于v 。同理，至多有 51277n 个元素小于v 。这样，以 v 为划分元素，产生的新数组至多有 51277n 个元素。当24n 时， 512117714nn。 另一方面，在整个执行过程中，递归调用 Select 函数一次，涉及规模为/ 7n，而下一次循环 Loop 涉及的数组规模为 1114 n 。程序中其他执行步的时间复杂度至多是 n 的倍数cn ，用( )T n 表示算法在数组长度为 n 的时间复杂度，则当24n 时，有递归关系 111( )()()714T nTnTncn 用数学归纳法可以证明， ( )14T ncn。所以时间复杂度是( )O n 。 （2）当3r 时，使用上述方法进行分析，可知在进行划分后数组 A 中有至多nn653232个元素。而递归关系为cnnTnTnT)65()31()(。若通过归纳法证明出有 ( )T nkcn的形式，用数学归纳法可以证明，cnnT28...
