首页 > 试题广场 >

分治法的基本思想?

[问答题]
分治法的基本思想?
添加回答
LYX_1129头像 LYX_1129
将一个较大的问题分为较小的子问题，化整为零。基本思路如下：
  1. 分解。将原问题划分为一些小问题，这些小问题与原问题具有相同的形式，只是规模更小。
  2. 递归求解。将子问题递归求解，不断向下直至触底，达到可以直接求解的程度。
  3. 合并。将子问题的解一步一步向上合并，最终得到原问题的解。
分治法的实现离不开递归式，在子问题平均划分的情况下，分治算法的时间复杂度通常可以表示为：
T（n）=aT（n/b）+f(n），其中a是子问题的个数，n/b是子问题的规模，f（n）是分解与合并的代价。
发表于 2020-09-18 21:08:17 回复(0)
提交观点

问题信息

分治
上传者：蜡蜡
难度：
1条回答 2761浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号