分治·减治·变治

xiaoxiao2021-02-28  31

A. 分治法(Divide and Conquer)

算法设计思想: 1. 分解:把问题递归分解为两个以上的子问题(子问题:与原问题性质相同,规模较小); 2. 求解:求解子问题(不再分解) 3. 合并:合并子问题的解,得到原问题的解;

相关算法: 1. 合并排序 2. 快速排序


B. 减治法(Decrease and Conquer)

算法设计思想: 1. 减小规模:递归减小子问题的规模(一个子问题) 2. 求解:求解子问题(不再减小规模) 3. 扩展:扩展子问题的解,获得原问题的解

与分治法的区别: 分治法:求解多个子问题,合并子问题解 减治法:求解一个子问题,扩展子问题解

减治法的分类: 1. 减常量法:减小常量规模,常为 1(减一法) 2. 减常因子法:减小常因子规模,常为 2(减半法) 3. 减可变规模法:每次减小的规模不同

相关算法: 1. 折半查找 2. 插入排序 3. 拓扑排序


C. 变治法(Transform and Conquer)

基于变换的思想,把问题变为更简单、更易求解的问题 变:变换问题 治:求解问题

相关算法: 1. 预排序 2. 堆排序

转载请注明原文地址: https://www.6miu.com/read-450255.html

最新回复(0)