《算法设计与分析基础(第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