白东程子末军 HANDONG UNIVERSITY OF TECIINOLOGY 计算机算法设计与分析 Design and Analysis of Computer Algorithms 第二章递归与分治策哈
计算机算法设计与分析 Design and Analysis of Computer Algorithms 第二章 递归与分治策略
山东程子太军 学习要点： SHANDONG UNIVERSITY OF TECHNOLOOY 3会诗3会合3会学3华A多器察 ·理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 ()二分搜索技术； (2)大整数乘法； ● (3)Strassen矩阵乘法； (4)棋盘覆盖； (5)合并排序和快速排序； ● (6) 线性时间选择； ● (7) 最接近，点对问题； (8) 循环赛日程表。 2025年4月3日 2
2025年4月3日 2 • 理解递归的概念。 • 掌握设计有效算法的分治策略。 • 通过下面的范例学习分治策略设计技巧。 • （1）二分搜索技术； • （2）大整数乘法； • （3）Strassen矩阵乘法； • （4）棋盘覆盖； • （5）合并排序和快速排序； • （6）线性时间选择； • （7）最接近点对问题； • （8）循环赛日程表。 学习要点:
归东程子末军 算法总体思想 SHANDONG UNIVERSITY OF TECHNOLOGY 器会空点会器空会的是 ●将要求解的较大规模的问题分割成k个更小规模的子问题。 对这k个子问题分别求解。如果子问题的规模仍然不够小， 则再划分为k个子问题，如此递归的进行下去，直到问题规 模足够小，很容易求出其解为止。 T(n) T(n/2) T(n/2) T(n/2) T(n/2) 2025年4月3日 3
2025年4月3日 3 ⚫ 将要求解的较大规模的问题分割成k个更小规模的子问题。 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ⚫ 对这k个子问题分别求解。如果子问题的规模仍然不够小， 则再划分为k个子问题，如此递归的进行下去，直到问题规 模足够小，很容易求出其解为止
算法总体思想 白东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 3会清会空会察 ●将求出的小规模的问题的解合并为一个更大规 模的问题的解，自底向上逐步求出原来问题的 解。 T(n) (n/4(n/4(n/4T(n/4)T(n/4(n/4T(n/4T(n/4)T(n/4T(n/4T(n/4(n/4)T(n/4T(n/4(n/4(n/4) 2025年4月3日
2025年4月3日 4 算法总体思想 ⚫ 将求出的小规模的问题的解合并为一个更大规 模的问题的解，自底向上逐步求出原来问题的 解。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4)
归本程子太军 SHANDONG UNIVERSITY OF TECHNOLOGY 会合会点会器空深会是会品 分治法的设计思想是，将一个难以直接解决的大 问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。 凡治众如治寡，分数是也。 孙子兵法 2025年4月3日
2025年4月3日 5 分治法的设计思想是，将一个难以直接解决的大 问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。 凡治众如治寡，分数是也。 -孙子兵法