《算法设计与分析基础(第3版)》部分习题答案

学号：______  姓名：________ 

P135

2.

 a. 为一个分治算法编写伪代码，该算法同时求出一个元素数组的最大元素和最小元素的值。

        解：算法：EXTREMUM(A[],EXTREMUM_MAX, EXTREMUM_MIN)

               //递归调用EXTREMUM函数来找出数组A[]的最大元素和

                 最小元素。

               //输入：数值数组A[]

               //输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MIN

               if()    //只有一个元素

                  EXTREMUM_MAXA[];

                  EXTREMUM_MINA[];

               else

                   if  //有两个元素

                      if 

                             EXTREMUM_MAX; EXTREMUM_MIN;

                      else 

                             EXTREMUM_MAX; EXTREMUM_MIN;

                   else 

                        EXTREMUM(,EXTREMUM_MAX_01, EXTREMUM_MIN_01);

                        EXTREMUM(,EXTREMUM_MAX_02, EXTREMUM_MIN_02);

                        if EXTREMUM_MAX_01 EXTREMUM_MAX_02

                           EXTREMUM_MAX = EXTREMUM_MAX_02;

                        If EXTREMUM_MIN_02 EXTREMUM_MIN_01

                           EXTREMUM_MIN = EXTREMUM_MIN_02;

b. 假设,为该算法的键值比较次数建立递推关系式并求解。

       解：

c. 将该算法与解决同样问题的蛮力法做一个比较

蛮力法时间时间复杂度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快。

5.1.3

a.为一个分治算法编写伪代码，该算法用来计算指数函数an的值，其中a>0, n是一个正整数。

//该算法使用分治法来计算an

Pow(a,n)

If n = 1

return a

else

p←pow(a,n/2);

If n mod 2 = 1

return p*p*a;

else

 return p*p;

b.建立该算法执行的乘法次数的递推关系式并求解

c.将该算法与解决同样问题的蛮力法做一个比较

蛮力法时间复杂度为n，分治法为,分治法速度明显要

高于蛮力法。

5.2

3. 举例说明快速排序不是一个稳定的排序算法

解：从小到大的快速排序：问题中给出的数据为从大到小，每次选择第一个数作

    中间值。

    例：数据9,7,6,7,10,7,7,3,2,1，当选择第一个数我中间操作数时，9和第

        4个7交换，元素7的稳定性就乱了。

6.4

11.任选一种语言实现三种高级排序算法——合并排序，快速排序和堆排序，然

   后针对规模为的数组研究它们的性能。对于每种规

模，再考虑以下三种情况：

a.区间内的整数所构成的随机生成文件。

b.整数的升序文件。

c.整数的降序文件。

合并排序：

图1.1

合并排序算法效率分析：

合并排序算法时间复杂度为O（NLogN），运行效率比较高，是一个稳定的排序算法。N=106时，时间也在1s左右。

快速排序：

图2.1 1000量级

图2.2 10000量级

图2.3 100000量级

图2.4 1000000量级

快速排序算法效率分析。

对于数据规模n<=104，程序能在1S内运行出来，对于n=105程序运行随机数据能在1S内运行出来，如果数据具有一定的顺序，则运行速度大大下降，对于n=106的数据，程序运行不出来。

对于快排 ，平均复杂度为O（NLogN），最坏情况为O（N2）。

堆排序。

运行结果：

堆排序算法复杂度分析

对N个元素建堆的时间复杂度为O(N)，删除堆顶元素的时间复杂度为O(logN)，尽管随着元素的不断删除，堆的调度越来越小，但是总的而言，删除堆所有元素的时间复杂度为O(NlogN)

故堆排序的时间复杂度为O(NlogN)，空间复杂度为O(1)

其实，堆排序是一个非常稳定的算法，最坏和平均情况下的时间复杂度都为O(NlogN)

此外，对于堆排序而言，数据的初始顺序对它的复杂度没有影响。不管数组初始时就是有序的还是逆序的，它都会先建堆，变成了堆序的性质。