分治算法设计技术______。

admin2013-05-11  33

问题 分治算法设计技术______。

选项 A、一般由三个步骤组成:问题划分、递归求解、合并解
B、一定是用递归技术来实现
C、将问题划分为庀个规模相等的子问题
D、划分代价很小而合并代价很大

答案A

解析 本题考查算法设计技术。分治方法是一种重要的算法设计技术(设计策略),该策略将原问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题;然后再合并其结果,最终得到原问题的解。分治算法往往用递归技术来实现,但并非必须。分治算法最理想的情况是划分为k个规模相等的子问题,但很多时候往往不能均匀地划分子问题。分治算法的代价在划分子问题和合并子问题的解上,根据不同的问题,划分的代价和合并的代价有所不同。例如归并排序中,主要的计算代价在合并解上,而在快速排序中,主要的计算代价在划分子问题上。
转载请注明原文地址:https://kaotiyun.com/show/rzRZ777K
0

相关试题推荐
最新回复(0)