分治算法设计技术（63)。（63) A．一般由三个步骤组成：问题划分递归求解合并解 B．一定是用递归

计算机 2018-05-08 22:23:21 递归,算法已帮助人

分治算法设计技术 (63)。

(63)

A．一般由三个步骤组成：问题划分、递归求解、合并解

B．一定是用递归技术来实现

C．将问题划分为k个规模相等的子问题

D．划分代价很小而合并代价很大

难度★★☆ 搜索

参考答案：A试题(63)分析本题考查算法设计技术。分治方法是一种重要的算法设计技术（设计策略），该策略将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题；然后再合并其结果，最终得到原问题的解。分治算法往往用递归技术来实现，但并非必须。分治算法最理想的情况是划分为k个规模相等的子问题，但很多时候往往不能均匀地划分子问题。分治算法的代价在划分子问题和合并子问题的解上，根据不同的问题，划分的代价和合并的代价有所不同。例如归并排序中，主要的计算代价在合并解上，而在快速排序中，主要的计算代价在划分子问题上。参考答案(63)A

分治算法设计技术 （63)。 （63) A．一般由三个步骤组成：问题划分 递归求解 合并解 B．一定是用递归