作者kib65060 (阿忠)
看板Grad-ProbAsk
标题Re: [理工] [资结] 98交大资讯联招
时间Tue Jan 18 21:11:39 2011
(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
1F:→ jameschou:我个人还是觉得如果只要判断polynomial而没要比大小 01/18 21:31
2F:→ jameschou:取lg来看是否为O(lgn)最快 而且其实取log这动作用心算也 01/18 21:32
3F:→ jameschou:很OK 纯属个人意见@@ 01/18 21:32