[理工] [資結] 98交大資訊聯招

看板Grad-ProbAsk作者boy5548 (小YO)時間15年前 (2011/01/18 10:57)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/3 (看更多)

請問98交大資結第4題的(2) 題目是這樣：Consider the following 15 functions.How many of them are polynimial bounded function? 我有問題的是這三個選項： (1)n! (2)n^(lglgn) (3)(lgn)^lgn 以下是我的想法 (1)我把他取lg後，變成lg(n!)=O(nlgn)，根據polynomial bounded定義，f(n)=O(n^k) => lg(f(n))=O(lgn)，只要lg(f(n))是O(lgn)，則f(n)為polynomial bounded。 nlgn≦C˙lgn = O(lgn)，C為正常數所以n!是polynomial bounded，請問這樣想是哪裡錯了? (2)將此函式取lg後，變成lglgn(lgn)≦C˙lgn = O(lgn)，C為正常數所以也是polynomial bounded，這樣想是哪裡錯? (3)一樣取lg後，變成lgn(lglgn)≦C˙lgn = O(lgn)，C為正常數所以也是polynimial bounded，請問是哪裡錯? 懇請各位指點謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.22.18.101

推

jameschou

01/18 11:20, , 1^F

01/18 11:20, 1^F

感謝已修正 ※ 編輯: boy5548 來自: 163.22.18.101 (01/18 11:55)

→

privatewind

01/18 13:16, , 2^F

01/18 13:16, 2^F

‣ 返回看板[ Grad-ProbAsk ] 研究

‣ 更多 boy5548 的文章

文章代碼(AID): #1DDG6OcI (Grad-ProbAsk)