算法导论习题答案

算法导论习题答案
3.1-1设f(n)与g(n)都是渐进非负函数。利用Θ记号的基本定义来证明max(f(n),g(n))=Θ(f(n)+g(n))。
证明:因为f(n)和g(n)都使渐进非负函数,同时假设存在这样的整数c1,c2和n0,使得:
0<=c1(f(n)+g(n))<=max(f(n)+g(n))<=c2(f(n)+g(n))成立。
令c2=1,则第3个不等式显然成立,因为两正数之和定大于两个中的最大值;再令c1=1/2,则第2个不等式也成立,因为两正数中最大的一个数定大于或等于两数的平均值;第1个不等式,因为f(n)与g(n)都使渐进非负,所以也显然成立。综上,既该等式确实成立。最后再根据Θ记号的定义可得:max(f(n),g(n))=Θ(f(n)+g(n))。

3.1-2 证明对任意实常数a和b,其中b>0,有
[2] (n+a)^b=Θ(n^b)
证明:要想证明上式成立,先要来证明等式:
[1] 0<=c1(n^b)<=(n+a)^b<=c2(n^b)
也就使说存在两个正常数c1,c2,使得当n充分大时(n+a)^b,能够被夹在c1(n^b)和c2(n^b)中间。显然,因为b>0,c1,c2已知为正常数,所以第一个等式:0<=c1(n^b)当n充分大时成立。接着,第二、三个等式分别除于(n^b)后得(n^b不可能为0):c1<=((n+a)/n)^b<=c2,进一步推得:c1<=(1+a/n)^b<=c2。又因为,a,b均为实常数,且当n充分大时,a/n趋向于0。所以,c1,c2分别可取值1/2,2,使得等式成立,等式(1)成立,也就证明了等式(2)成立。

3.1-3 解释为什么“算法A的运行时间至少是O(n²)”这句话是无意义的。
答:根据O记号的定义可知,它是用来表示上界的,当用它作为算法的最坏情况运行时间的上界时,就有对任意输入的运行时间的上界。我们说“一个算法A的运行时间为O(n²)”,它表示的是说该算法运行时间的一个上界,适用于每个输入的运行时间,这与题中的“至少是”表达的是同一个意思。所以题中的话是无意义的。

3.1-42^(n+1)=O(2^n)成立吗?2^(2n)=O(2^n)成立吗?
答:第一个成立;第二个不成立。
因为,[1]0<=2^(n+1)<=c(2^n),当n充分大时,第一个等式0<=2^(n+1)显然成立。第二个等式两边分别除以2^n,得:2<=c,即c>=2。即存在这样两个正常数c(c可取大于等于2的任意一个常数)使得等式(1)成立,所以得:2^(n+1)=O(2^n)成立。
同理,0<=2^(2n)<=c(2^n),第二个等式两边除以(2^n)得:2^n<=c,因为c为正常数,当n充分大时,不存在这样的c使之成立,也就证明了,2^(2n)=O(2^n)不成立。

3.1-5 证明定理3.1
定理3.1 在o中表示当n趋于无穷大时,函数f(n)相对于g(n)来说就不重要了。
证明:根据o记号的定义:对f(n)=o(g(n)),界o<=f(n)<=cg(n)对所有常数c>0成立,这句话说明了函数g(n)的增长速度要快于f(n),当n趋向无穷大时,差距就更大了。所以等式3.1时成立的。

3.1-6证明:一个算法的运行时间是Θ(g(n))当且仅当其最坏情况运行时间O(g(n)),且最佳情况运行时间是Ω(g(n))。
证明:一个算法的运行时间是Θ(g(n)),则说明存在这样两个正常数c1,c2使得(当n充分大时):0<=c1g(n)<=f(n)<=c2g(n),因而等式0<=c1g(n)<=f(n)成立,完整地说,即存在正常数c1和n0,使得对所有n>=n0,有0<=c1g(n)<=f(n)成立。所以,根据Ω记号的定义得:该算法的最佳情况运行时间是Ω(g(n))。同理,因为等式0<=f(n)<=c2g(n)成立,所以该算法的最坏情况运行时间是O(g(n))。综上,证得该说法成立。

3.1-7 证明o(g(n))∩ω(g(n))是空集。
证明:根据o(g(n))={ f(n):对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0<=f(n)<=cg(n)},而集合ω(g(n))={ f(n):对任意正常数c>0,存在常数n0>0,使对所有n>=n0,有0<=c(g(n))
[1] 0<=f(n)<=cg(n)¹,o(g(n))
[2] 0<=cg(n)²
推得:
[1] g(n)¹>=(1/c)f(n)
[2] g(n)²<(1/c)f(n)
可得,o(g(n))和ω(g(n))两集合没有共有部分。即证得o(g(n))∩ω(g(n))是空集。

3.1-8可以将我们的表示法扩展到有两个参数n和m的情形,其中n和m的值可以以不同的速率,互相独立地趋于无穷。对给定的函数g(n,m),O(g(n,m))为函数集
O(g(n,m))={ f(n,m):存在正整数c,n0和m0,使对所有n>=n0或m>=m0,有0<=f(n,m)<=cg(n,m)}。
给出对应的Ω(g(n,m))和Θ(g(n,m))的定义。
[1] Ω(g(n,m))={ f(n,m):存在正整数c,n0和m0,使对所有n>=n0或m>=m0,有0<=cg(n,m)<=f(n) }
[2] Θ(g(n,m))={ f(n,m):存在正整数c1,c2,n0和m0,n0和m0,使对所有n>=n0或m>=m0,有0<=c1g(n,m)<=f(n)<=c2g(n,m)}

  

爱华网本文地址 » http://www.aihuau.com/a/25101015/254643.html

更多阅读

施工组织与流水施工习题答案

一单选题1.下述施工组织方式中日资源用量最少的是( A )。A、依次施工B、平行施工C、流水施工D、搭接施工2.采用( B)组织方式,每天投入的资源量大,施工现场管理复杂。A.依次施工B.平行施工C.流水施工D.间隔施工3.在下列组织施工的方式

计算机网络第5版 习题答案5-6章 谢希仁编著

引用跃 的 计算机网络(第5版) 习题答案(5-6章) 谢希仁 编著第1章-第4章答案第五章 传输层5—01试说明运输层在协议栈中的地位和作用,运输层的通信和网络层的通信有什么重要区别?为什么运输层是必不可少的?

快速排序-算法导论版本 算法导论 排序网络

快速排序算法和合并排序算法一样,也是基于分治模式。对子数组A[p...r]快速排序的分治过程的三个步骤为:分解:把数组A[p...r]分为A[p...q-1]与A[q+1...r]两部分,其中A[p...q-1]中的每个元素都小于等于A[q]而A[q+1...r]中的每个元素都大于

新编大学英语第二版第二册 习题答案

新编大学英语(第二册)习题答案《新编大学英语(第二版)》由浙江大学编著,应惠兰主编,外语教学与研究出版社出版,刊出其习题答案是为了奉献给我三合村在读大学生参考,更多内容请点击博客“首页”。Key toExercises of Unit 1Part Two Readi

政治经济学 第一章导论习题及参考答案

一 、名词解释劳动、劳动对象、劳动资料、生产资料、生产力、生产关系、生产资料所有制、社会经济制度、经济体制、经济规律二 、单项选择题⒈ 作为一切社会关系中最基本的关系是()① 分配关系 ② 消费关系 ③ 生产关系 ④ 交换关系⒉

声明:《算法导论习题答案》为网友别后天涯各自愁分享!如侵犯到您的合法权益请联系我们删除