您的位置: 首页 > 文章 > 算法设计与分析【2】分治算法 算法设计与分析【2】分治算法 分类: 文章 • 2024-01-06 16:24:16 分治 基本思想 影响算法复杂度的因素 经典案例 1 二分检索 设计思想 伪码 2 二分归并 设计思想 伪码 3 汉诺塔 设计思想 伪码 4 快速排序 设计思想 伪码 实例 减少子问题个数案例:大数相乘 设计思想 5 快速傅里叶变换(信号平滑处理) 问题描述 设计&分析 参考材料 基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,递归或迭代地解这些子问题,然后将各子问题的解综合得到原问题的解。 影响算法复杂度的因素 子问题的个数 子问题合并的工作量 改进分治算法有两个途径: 减少子问题的个数 增加预处理 经典案例 1 二分检索 设计思想 伪码 2 二分归并 设计思想 伪码 3 汉诺塔 设计思想 伪码 4 快速排序 设计思想 伪码 实例 减少子问题个数案例:大数相乘 设计思想 5 快速傅里叶变换(信号平滑处理) 问题描述 设计&分析 参考材料 mooc算法分析与设计