作者kaemu1006 (kaemu1006)
看板Grad-ProbAsk
标题[理工] 演算法 Big O相关问题
时间Tue Oct 27 19:18:10 2020
https://i.imgur.com/j0aWhIN.png
请问解答给lg n的例子，考虑log的定义n必须大於0，f(n)<=g(n) && 2^f(n)>2^g(n)我的理
解如下
不知道是否可以推翻解答？ 谢谢大家
https://i.imgur.com/66hZsC2.png
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.140.27.140 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1603797492.A.2F3.html
1F：推 gua0313: 在下浅见 大大对的 但题目谈论Big O 是在N趋於很大的情况 10/27 20:51
2F：→ gua0313: 下 10/27 20:51
3F：推 kyuudonut: 不 ... 题目只是问是否 "存在" 此 function 10/27 20:59
4F：→ kaemu1006: 感谢回答 10/27 23:39
5F：推 asd3136396: f(n)带n, g(n)带2n 10/28 03:31
6F：推 asd3136396: 解答应该是没错啦 f(n)=O(g(n)) 10/28 03:34
7F：→ asd3136396: 应该是f(n) <= c*g(n) 10/28 03:34
8F：推 joywilliamjo: 解答没有错啊，lgn^2记得次方项会被拉到常数 10/29 04:34
9F：推 zuchang: 叙述改成always 的话就是错 这题蛮常拿来玩文字游戏的 11/02 16:48