第2章 递归与分治_作业答案.ppt

课后练习 练习1 给定数组a 0 n 1 试设计一个分治法算法 找出a 0 n 1 中元素最大值和最小值 写出该算法时间函数T n 的递推关系式 分析该算法的时间复杂度和空间复杂度 算法的基本思想 如果数组中只有一个元素 则该元素即是数组中最大的元素 否则将数组对分为前半部分和后半部分 用同样的方法求数组前半部分的最大值max1 用同样的方法求数组后半部分的最大值max2 若max1 max2 则max1为数组中的最大值 否则max2为数组中的最大值 具体执行过程 求最大值 intMAXA A i j inti j max 0 max1 0 max2 0 intA if i j max A i else 求数组前半部分的最大值max1 max1 MAXA A i i j 2 求数组后半部分的最大值max2max2 MAXA A i j 2 1 j if max1 max2 max max1 elsemax max2 returnmax 课后练习 练习2 分析如下时间函数的复杂度 并说明原因 1 利用递归树说明以下时间函数的复杂度 2 利用主定理说明以下时间函数的复杂度 T n 16T n 4 nT n T 3n 7 1T n 3T n 4 nlogn 练习2 分析如下时间函数的复杂度 并说明原因 1 利用递归树说明以下时间函数的复杂度 递归树的高度为 log4n 1 除去叶子结点 树有log4n层 每层结点总数为 最后一层叶子结点数 2 利用主定理说明以下时间函数的复杂度 T n 16T n 4 nT n T 3n 7 1T n 3T n 4 nlogn 定理 主定理 a 1且b 1是常数 f n 是一个函数 T n 由如下的递推式定义 T n aT n b f n 式中 n b指 n b 或 n b 则T n 有如下的渐近界 1 若对于某常数 0 有f n O nlogba 则T n nlogba 2 若f n nlogba 则T n nlogbalogn 3 若对于某常数 0 有f n nlogba 且对于某个常数c 1和所有足够大的n 有af n b cf n 则T n f n 练习3 分析Strassen矩阵乘法在时间效率上有何改进 为什么 Strassen矩阵乘积分治算法中 用了7次对于n 2阶矩阵乘积的递归调用和18次n 2阶矩阵的加减运算 由此可知 该算法的所需的计算时间T n 满足如下的递归方程 T n O nlog7 O n2 81 较大的改进 课后练习 练习4 划出下列序列在快速排序过程中一次划分的具体步骤 21254925 1608 一次划分的过程 21 08 25 49 25 16 初始关键字 08 25 49 25 16 08 25 49 25 16 08 25 49 25 16 21 21 21 08 25 49 25 16 21 08 25 49 25 16 21 pivotkey 一次交换 二次交换 三次交换 四次交换 完成一趟排序 low high low high high low 课后练习 练习5 算法实现题2 8 教材第42页 集合划分问题 要求 设计算法 写出该算法时间函数T n 的递推关系式 分析其时间复杂度和空间复杂度 关于集合划分问题的分析 例如 集合 1 2 3 有五个划分 1 2 3 1 2 3 1 3 2 1 2 3 1 2 3 算法设计要求 给定正整数n和m 计算出n个元素的集合 1 2 n 可以划分为多少个不同的由m个非空子集组成的集合 数据输入 由文件input txt提供输入数据 文件的第1行是元素个数n和非空子集数m 结果输出 程序运行结束时 将计算出的不同的由m个非空子集组成的集合数输出到文件output txt中 递归公式 设n个元素的集合可以划分为F n m 个不同的由m个非空子集组成的集合 F n m 1 whenn 0 n m n 1 orm 1F n m 0 whenn m否则F n m F n 1 m 1 m F n 1 m 考虑3个元素的集合 可划分为 1个子集的集合 1 2 3 2个子集的集合 1 2 3 1 3 2 2 3 1 3个子集的集合 1 2 3 F 3 1 1 F 3 2 3 F 3 3 1 如果要求F 4 2 该怎么办呢 A 往 里添一个元素 4 得到 1 2 3 4 B 往 里的任意一个子集添一个4 得到 1 2 4 3 1 2 3 4 1 3 4 2 1 3 2 4 2 3 4 1 2 3 1 4 F 4 2 F 3 1 2 F 3 2 1 2 3 7 课后练习 选做 练习6 假设有n个项的数组A 每个项具有一个不同的数 告诉你值A 1 A 2 A n 的序列是单峰的 对于某个在1与n之间的下标p 数组项的值增加到A中的位置p 然后剩下的过程减少直到位置n 要求 利用分治策略设计一个算法 读尽可能少的元素 找到这个 顶峰 元素p 分析该算法的时间复杂性 问题分析 何为 单峰 对于某个在1与n之间的下标p 数组项的值增加到A中的位置p 然后剩下的过程减少直到位置n 即在A 1 到A n 的n个数中 只有一个极大值A p A p 前的元素均小于A p 并按升序排列 A p 后的元素均小于A p 并按降序排列 分治法思想 查看A n 2 值 分析其是出现在上坡上 A n 2 在A p 之前 还是下坡上 A n 2 在A p 之后 如果A n 2 1 A n 2 A n 2 1 那么n 2项一定严格位于p的前面 因此可以在n 2 1项到n项之间递归地继续下去 如果A n 2 1 A n 2 A n 2 1 那么n 2项一定严格位于p的后面 因此可以在1项到n 2 1项之间递归地继续下去 如果A n 2 比A n 2 1 和A n 2 1 都大 顶峰项实际上就等于A n 2 具体算法 伪代码 intDanfeng intA intm intn 求单峰数组中的顶峰值intk m n 2 if k m 时间复杂性分析 该算法的时间函数的递推式为 该算法的时间复杂度为 O log2n 课后练习 选做 练习7 假设你正在为一个小的投资公司咨询 他们有下面类型的问题想要一次又一次的求解 这个问题的一个典型实例如下所述 他们正在做一项模拟 在这项模拟中他们从过去的某点开始对一只给定的股票连续看n天 让我们把这些天记为数i 1 2 n 对每天i 他们有当天这只股票每股的价格p i 简单起见 假设这个价格在一天之内是固定的 假设在这个时间区间内 某天他们想买1000股并且在以后的某天卖出所有这些股 他们想知道 为了挣到最多的钱 他们应该什么时候买并且什么时候应该卖 问题分析 举例说明 利用分治策略设计一个算法 举例 假设n 3 p 1 9 p 2 1 p 3 5 那么应该得出 2买 3卖 的结论 即 在第2天买并且在第3天卖意味着每股将挣4美元 是这个期间最大的收益 问题分析 存在一个简单的算法 时间复杂度是O n2 对所有的买天 卖天构成的对进行尝试 看看哪个对能使用户挣到最多的钱 假设在第i天买 第j天卖可以获得最大收益 最优解 怎样在O nlog2n 时间找到正确的i和j 一共有n天的数据 即p 1 p 2 p i p i 1 p n 1 p n 设S是1天 n 2天的集合 S 是n 2 1 n天的集合 分治法策略 或者有一个最优解使投资者在n 2结束时持有这只股票 第i天买入股票 此时i n 2 第j天卖出股票 此时j n 2 1 或者没有 最优解在集合S中 i与j均 n 2 用户可以在前n 2天内买入股票并卖出 或者最优解在集合S 中 i与j均 n 2 1 用户可以在后n 2天内买入股票并卖出 则算法是在下面三个可能的解中最好的 S上的最优解S 上的最优解p j p i 的最大值 对所有的i S且j S 前两个选择中的每一个在T n 2 时间内被递归地计算 第三个选择通过找S中的最小与S 中的最大而计算 该操作需要O n 时间 则运行时间的递推关系式是 则算法的时间复杂度为 O nlog2n 具体算法 伪代码 intMaxProfit intp intm intn 求第m到第n天内一次买卖股票的最大收益inti m j m n 2 1 在第i天买入股票 并在第j天卖出股票intk intmax1 max2 max3 三个可能的