作者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/m.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