[理工] 98交大資結

[boy5548 (小YO)]

請問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:polynomial取完以後應該要是 O(logn) = =
感謝 已修正
※ 編輯: boy5548         來自: 163.22.18.101        (01/18 11:55)
→ privatewind:定義再看一次@.@ 你會發現你沒法取C...