内容发布更新时间 : 2024/12/25 12:39:27星期一 下面是文章的全部内容请认真阅读。
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