[理工] 时间复杂度

楼主: gpsmelody07 (YC)   2018-10-22 15:30:10
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
作者: wei12f8158 (WEI)   2018-10-22 16:09:00
第一个是True,洪逸的答案打错了https://i.imgur.com/p2rJI97.jpg这林立宇的版本
作者: skyHuan (Huan)   2018-10-22 17:07:00
#1Rjqdh3O (Grad-ProbAsk)345我觉得跟nannnnn大在这篇留言提到的情形一样,如果把函数取log(就是你提到的变小)比大小一定要有little-o的关系,就是分得出绝对等级大小的关系,才能保证原函数的大小关系是一样的反过来想,所以变大之后的关系不一定会跟原来关系一样
楼主: gpsmelody07 (YC)   2018-10-23 08:32:00
了解,谢谢

Links booklink

Contact Us: admin [ a t ] ucptt.com