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

2017-2018-2学期《算法分析A》作业

作业一

学号：______ 姓名：________

P135 2.

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

最小元素的值。

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

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

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

//输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MIN if( )

//只有一个元素

EXTREMUM_MAX A[ ]; EXTREMUM_MIN A[ ]; 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;

1 / 7

2017-2018-2学期《算法分析A》作业

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，分治法为 ,分治法速度明显要 高于蛮力法。

2 / 7

2017-2018-2学期《算法分析A》作业

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

合并排序算法效率分析：

3 / 7

2017-2018-2学期《算法分析A》作业

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

图2.1 1000量级

图2.2 10000量级

4 / 7

2017-2018-2学期《算法分析A》作业

图2.3 100000量级

图2.4 1000000量级

快速排序算法效率分析。

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

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

堆排序。 运行结果：

5 / 7

本文来源：https://www.bwwdw.com/article/a4qh.html