文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 算法设计与分析基础课后习题答案(中文版)
侵权投诉

算法设计与分析基础课后习题答案(中文版)

习题 3.1 4. a.设计一个蛮力算法,对于给定的 x0,计算下面多

项式的值: P(x)=anxn+an-1xn-1+…+a1x+a0 并确定该算法的最差效率类型. b.如果你设计的算法属于Θ (n2),请你为该算法设计一个线性的算法. C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢? 解: a. Algorithms BruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式 p 在给定点 x 的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值 x //输出: 多项式 p 在给定点 x 的值 p=0.0 for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+P[i]*power return p 算法效率分析: 基本操作:两个数相乘,且 M(n)仅依赖于多项式的阶 n M ( n) 1 i i 0 j 1 i 0 n i n

n(n 1) ( n 2 ) 2

b. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from the lowest term to the highest and compute xi by using xi-1. Algorithms BetterBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式 p 在给定点 x 的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值 x //输出: 多项式 p 在给定点 x 的值 P=P[0] power=1 for i←1 to n do power←power*x p←p+P[i]*power return p 基本操作乘法运算总次数 M(n): M (n) 2 2n (n) i 1 n

c. 不 行 . 因 为 计 算 任 意 一 个 多 项 式 在 任 意 点 x 的 值 , 都 必 须 处 理 它 的 n+1 个 系 数 . 例 如 : (x=1,p(x)=an+an-1+..+a1+a0,至少要做 n 次加法运算) 5.应用选择排序对序列 example 按照字母顺序排序.

算法设计与分析基础课后习题答案(中文版)

上一页第10页

你可能喜欢

  • 计算机算法设计与分析
  • 中南大学
  • C语言经典算法
  • C语言谭浩强
  • 排序算法总结
  • C语言函数
  • C语言源代码
  • 语言分析

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email