博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
《算法导论》读书笔记--第三章函数的增长 课后题
阅读量:5878 次
发布时间:2019-06-19

本文共 3008 字,大约阅读时间需要 10 分钟。

本章的课后题看一下即可,比较平凡。

3.1渐近记号

引用一下别人的答案,非常感谢:

原文地址:

|概念回顾|

当输入规模大到使只有运行时间的增长量级有关时,就使在研究算法的渐进效率

几个重要渐进记号的定义:

  • Θ(g(n))={ f(n): 存在正常数c1,c2和n0,使对所有的n>=n0,有0<=c1g(n)<=f(n)<=c2g(n) }
  • O(g(n))={ f(n): 存在正常数c和n0,使对所有n>=n0,有0<=f(n)<=cg(n) }
  • Ω(g(n))={ f(n): 存在正常数c和n0,使对所有n>=n0,有0<=cg(n)<=f(n) }
  • o(g(n))={ f(n): 对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0<=f(n)<=cg(n) }
  • ω(g(n))={ f(n): 对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0<=cg(n)<f(n) }
|习题解答|

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-4  2^(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))<f(n) }。在同等条件下有以下两个等式:

[1] 0<=f(n)<=cg(n)¹,o(g(n))

[2] 0<=cg(n)²<f(n),  ω(g(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) }

3.2标准记号

下面这个答案比较靠谱,引用一下别人的答案,非常感谢:

3.2-2

3.2-3

非常遗憾的是,一个方向没有证出来。利用斯特林公式就容易证明了。关于斯特林公式;

 

 

3.2-4

前者不是多项式有界的,后者是多项式有界的。

3.2-5

第二个,因为第二个不过就是lg*n – 1 显然比第一个大。

3.2-6

显然,代入即可。

3.2-7

数学归纳法可验证。

3.2-8

这个问题可以将左边去ln,再进行推导。

思考题

题目已经解决了,公式太多不打了。

转载于:https://www.cnblogs.com/batteryhp/p/5011778.html

你可能感兴趣的文章
XML 节点类型
查看>>
驯服 Tiger: 并发集合 超越 Map、Collection、List 和 Set
查看>>
Winform开发框架之权限管理系统改进的经验总结(3)-系统登录黑白名单的实现...
查看>>
Template Method Design Pattern in Java
查看>>
MVC输出字符串常用四个方式
查看>>
LeetCode – LRU Cache (Java)
查看>>
JavaScript高级程序设计--对象,数组(栈方法,队列方法,重排序方法,迭代方法)...
查看>>
【转】 学习ios(必看经典)牛人40天精通iOS开发的学习方法【2015.12.2
查看>>
nginx+php的使用
查看>>
在 ASP.NET MVC 中使用异步控制器
查看>>
SQL语句的执行过程
查看>>
Silverlight开发历程—动画(线性动画)
查看>>
详解Linux中Load average负载
查看>>
HTTP 协议 Cache-Control 头——性能啊~~~
查看>>
丢包补偿技术概述
查看>>
PHP遍历文件夹及子文件夹所有文件
查看>>
WinForm程序中两份mdf文件问题的解决
查看>>
【转】唯快不破:创业公司如何高效的进行产品研发管理
查看>>
程序计数器、反汇编工具
查看>>
Android N: jack server failed
查看>>