习题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

算法设计与分析基础课后习题答案(中文版)_工学_高等教育_教育专区。算法设计与分析基础课后习题答案(中文版)Program 算法设计与分析基础中文版答案习题 1.1 5.....
算法设计与分析基础课后... 44页 1下载券算法设计与分...清华大学出版社 课后习题...
算法设计与分析基础习题参考答案_IT/计算机_专业资料。levtin 潘彦译算法教程的详细参考答案。习题1.1 5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正...
算法分析与设计课后习题答案Wklv oh frqwdlqv wkh h{huflvhv/ klqwv/ dqg vroxwlrqv iru Fkdswhu 44 ri ...
算法设计与分析习题答案1-6章_理学_高等教育_教育专区。习题 1 1. 图论诞生... 算法设计与分析第二版课... 37页 免费 算法设计与分析基础课后... 41页 ...
算法设计与分析习题答案1-6章_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 算法设计与分析习题答案1-6章_理学_高等教育_教育专区。习题 1 1....
算法设计与分析第二版课后习题解答_理学_高等教育_教育专区。算法设计与分析基础课后练习答案习题 1.1 4.设计一个计算 的算法,n 是任意正整数。除了赋值和比较...
算法设计与分析复习题目及答案_工学_高等教育_教育专区。一。选择题 1、二分...(要求:分别 给出 divide、conquer、combine 这三个阶段所花的时间,并在此基础上...
2013《计算机算法设计与分析》习题及答案_工学_高等教育_教育专区。《计算机算法设计与分析》习题及答案 2013 秋 1 《计算机算法设计与分析》习题及答案 一.选择...
算法设计与分析习题解答_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 算法设计与分析习题解答_计算机软件及应用_IT/计算机_专业资料。...
热门文档