推 boy5548:你的講解很詳細 謝謝!! 01/18 14:05
推 karaokstar:推周哥！ 01/31 02:07
※ 引述《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，請問是哪裡錯?
: 懇請各位指點 謝謝
我剛推文的意思其實就是說
這三題你算出來的都明顯比O(lgn)大了呀
所以這三個都不是polynomial了!!
你的C根本無法取到
以下跟你說明:
(1) n!取log的確可看出是O(nlgn)沒錯
但是沒有任何一個C可以使nlgn恆小於等於C˙lgn
(因為假設你任取了一個C,那麼只要取n=C+1的時候 nlogn就會>C˙logn了)
(2)(3)也同理
你取lg都沒算錯
但是只要你算出來的數比lgn還多非常數倍以上(比如說lglgn,n,n^2之類的),
那就沒有任何一個C可以寫成C˙lgn來把你的數bound住
再說更簡單一點就是
你取log以後 只要除了lgn以外 還帶有"n" 無論是lgn或什麼的
那就必定不是polynomial了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.226.226