Re: [心得] Master theorem 不能套用的題目

看板Grad-ProbAsk作者 (J.K.Lee)時間6年前 (2017/10/11 14:21), 6年前編輯推噓2(2推 0噓 0→)
留言2則, 2人參與, 6年前最新討論串2/3 (看更多)
在FRAXIS提供的文件中 https://goo.gl/t5ZSz6 p.1 Exercise 1 (YZU CSIE 90) 1. Prove or disprove n^[2 + sin(n)/lg n] = O(n^2) 我算出的結果與文件中相反，請問我哪裡錯了? consider n>1 sin(n)/lg n <= 1/lg n n^[sin(n)/lg n] <= n^[1/lg n] = [2^(lg n)]^[1/lg n] = 2^[(lg n)*(1/lg n)] = 2 n^[2 + sin(n)/lg n] = n^2 * n^[sin(n)/lg n] <= n^2 * 2 所以 n^[2 + sin(n)/lg n] = O(n^2) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.61.137 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1507702885.A.9EB.html
推
10/11 17:08, 6年前 , 1F
第一個等式就不對 sin的值域在-1~1之間
10/11 17:08, 1F
那改成這樣如何? ※ 編輯: JKLee (111.248.67.183), 10/12/2017 00:08:40
推
10/12 05:32, 6年前 , 2F
你是對的 我的答案不對
10/12 05:32, 2F
‣ 更多 JKLee 的文章
文章代碼(AID): #1PtRXbdh (Grad-ProbAsk)
‣ 更多 JKLee 的文章
文章代碼(AID): #1PtRXbdh (Grad-ProbAsk)