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