→ jameschou:我個人還是覺得如果只要判斷polynomial而沒要比大小 01/18 21:31
→ jameschou:取lg來看是否為O(lgn)最快 而且其實取log這動作用心算也 01/18 21:32
→ jameschou:很OK 純屬個人意見@@ 01/18 21:32
(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