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

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

习题1.4

1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i个元素(1<=i<=n)

b.删除有序数组的第i个元素(依然有序) hints:

a. Replace the ith element with the last element and decrease the array size of 1

b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (―lazy deletion‖)

第2章 习题2.1

7.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:

a. 这个断言是正确的。它指出如果t(n)的增长率小于或等于g(n)的增长率,那么 g(n)的增长率大于或等于t(n)的增长率

由 t(n)≤c·g(n) for all n≥n0, where c>0

1

则:()t(n) g(n) for all n≥n0

cb. 这个断言是正确的。只需证明 ( g(n)) (g(n)), (g(n)) ( g(n))。 设f(n)∈Θ(αg(n)),则有:

f(n) c g(n) for all n>=n0, c>0 f(n) c1g(n) for all n>=n0, c1=cα>0

即:f(n)∈Θ(g(n))

又设f(n)∈Θ(g(n)),则有:f(n) cg(n) for all n>=n0,c>0

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

上一页第4页

你可能喜欢

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

热门文档

相关文档

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