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

《算法设计与分析基础（第3版）》部分习题答案 2022-2022-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 2022-2022-2学期《算法分析A》作业 b. 假设 ,为该算法的键值比拟次数建立递推关系式并求解。

解： c. 将该算法与解决同样问题的蛮力法做一个比拟蛮力法时间时间困难度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快 5.1.3a. 为一个分治算法编写伪代码，该算法用来计算指数函数an的值，其中a>0, n是一个正整数//该算法运用分治法来计算an Pow(a,n) If n = 1return a elsep←pow(a,n/2); If n mod 2 = 1 return p*p*a; else return p*p; b. 建立该算法执行的乘法次数的递推关系式并求解 c. 将该算法与解决同样问题的蛮力法做一个比拟 蛮力法时间困难度为n，分治法为 ,分治法速度明显要 高于蛮力法 2 / 7 2022-2022-2学期《算法分析A》作业 5.23. 举例说明快速排序不是一个稳定的排序算法解：从小到大的快速排序：问题中给出的数据为从大到小，每次选择第一个数作 中间值。

例：数据9,7,6,7,10,7,7,3,2,1，中选择第一个数我中间操作数时，9和第 4个7交换，元素7的稳定性就乱了 6.4 11.任选一种语言实现三种高级排序算法——合并排序，快速排序和堆排序，然 后针对规模为 ， ， ， 的数组探究它们的性能对于每种规模，再考虑以下三种状况：a. 区间内的整数所构成的随机生成文件 b.整数 ， ， ， 的升序文件 c.整数 的降序文件合并排序： 图1.1合并排序算法效率分析： 3 / 7 2022-2022-2学期《算法分析A》作业 合并排序算法时间困难度为O〔NLogN〕，运行效率比拟高，是一个稳定的排序算法N=106时，时间也在1s左右 快速排序： 图2.1 1010量级 图2.2 10100量级 4 / 7 2022-2022-2学期《算法分析A》作业 图2.3 101000量级 图2.4 1010000量级快速排序算法效率分析对于数据规模n<=104，程序能在1S内运行出来，对于n=105程序运行随机数据能在1S内运行出来，如果数据具有一定的顺序，则运行速度大大下降，对于n=106的数据，程序运行不出来。

对于快排 ，平均困难度为O〔NLogN〕，最坏状况为O〔N2〕 运行结果： 5 / 7 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第6页 共6页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页。