Re: [理工] [資結] 98交大資訊聯招
(2)(3)我會這樣解
O(n^(lglgn)) vs O(n^k)
同取log變成 => O(lgn*lglgn) vs O(klgn)
這裡可以看到當n無限大的時候 lglgn > k
所以(2)不是polynomial bounded
O((lgn)^lgn) vs O(n^k)
同理可以算到 => O(lgn*lglgn) vs O(klgn)
接著同上面了
考交大這種簡答題不需要推導的時候這樣想我覺得滿快的
有錯請指教，祝各位考生加油了!
※ 引述《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: 140.112.28.118
→
01/18 21:31, , 1F
01/18 21:31, 1F
→
01/18 21:32, , 2F
01/18 21:32, 2F
→
01/18 21:32, , 3F
01/18 21:32, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：