举一反三
- 动态规划算法本质上是空间换时间的算法,每一个子问题只解一次,存储子问题结果,避免重复计算。 A: 正确 B: 错误
- 下面有关动态规划算法错误的是() A: 动态规划算法本质上是时间换空间的算法 B: 动态规划算法的每一个子问题只解一次,存储子问题结果,避免重复计算。 C: 贪心和递推算法是线性解决问题,动态规划则是全面分阶段地解决问题。 D: 状态转移方程表示状态间的递推关系,也是子问题间的递推关系。
- 动态规划是一种将问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
- 动态规划的实质是分治思想和解决( ),因此它将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题。
- 中国大学MOOC:设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法.算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解.算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解.算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用http://i1.chinesemooc.org/course/formula/201512/3153cde106933f7fb002c4b8738f4c25.png时间将子问题的解综合得到原问题的解.要求在上述三个算法中选择最坏情况下时间复杂度最低的算法,需要选择哪个算法?
内容
- 0
中国大学MOOC: 设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. 算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. 算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解. 算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用http://i1.chinesemooc.org/course/formula/201512/3153cde106933f7fb002c4b8738f4c25.png时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法,需要选择哪个算法?
- 1
设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. 算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. 算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解. 算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法,需要选择哪个算法?https://p.ananas.chaoxing.com/star3/origin/d42cf4fc49501f223442d7f3184b4555.png
- 2
设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. __算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. __算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解.
- 3
关于动态规划法,下述不正确的是( )。 A: 动态规划对子问题只需要计算一次,因为动态规划解决的问题具有无重复子问题性质 B: 动态规划对子问题只需要计算一次,因为在计算的过程中,动态规划策略会将所有的子问题的解计算出来并存储在一张表中,不管将来是否用到 C: 动态规划通常用来求解最优解的问题 D: 动态规划策略的核心思想是维护一张存储所有子问题结果的表
- 4
设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. 算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. 算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解. 算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用[img=53x28]18039e0e50c75e0.png[/img]时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法,需要选择哪个算法? A: 1 B: 2 C: 3 D: 都不对