作者gpsmelody07 ()
看板Grad-ProbAsk
标题[理工] 时间复杂度
时间Mon Oct 22 15:30:10 2018
http://i.imgur.com/kNrTv2u.jpg
问选项(1)为什麽是False
另外想问(3)(4)(5)
常见的运算中，是不是只有取指数时不一定会维持原本的symbol，其他大多数运算都会维持？(如34取根号与lg都没变)
http://i.imgur.com/PK0HFJY.jpg
我知道O(f(n))+θ(f(n))=θ(f(n))
但这意味着O(f(n))+θ(f(n))=O(f(n))是错的吗？
因为题目只问对错，没要找最适当的symbol
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.248.18.82
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1540193413.A.F09.html
1F：推 wei12f8158: 第一个是True，洪逸的答案打错了 10/22 16:09
3F：→ wei12f8158: 这林立宇的版本 10/22 16:11
5F：→ skyHuan: 345我觉得跟nannnnn大在这篇留言提到的情形一样，如果把 10/22 17:07
6F：→ skyHuan: 函数取log(就是你提到的变小)比大小一定要有little-o的 10/22 17:07
7F：→ skyHuan: 关系，就是分得出绝对等级大小的关系，才能保证原函数的 10/22 17:07
8F：→ skyHuan: 大小关系是一样的 10/22 17:07
9F：→ skyHuan: 反过来想，所以变大之後的关系不一定会跟原来关系一样 10/22 17:09
10F：→ gpsmelody07: 了解，谢谢 10/23 08:32
11F：→ GeniusPuddin: 4应该不对欧 取g(n)=2,f(n)为一个小於1大於0的函数 02/05 00:31
12F：→ GeniusPuddin: f取log之後直接就可以负到天荒地老 不符合大O的定义 02/05 00:31
13F：→ GeniusPuddin: 取log跟次方应该都要考虑一下有没有例外状况 02/05 00:33
14F：→ GeniusPuddin: 觉得是TFTFF吧 02/05 00:33