作者asdd (我爱胖颖颖)
看板Examination
标题[考题] 102年关务 资料结构
时间Mon Apr 1 18:50:04 2013
下列哪两个叙述是错的
(A)0.5n^2+100n=O(n^2) (B)1000=O(1) (C)0.5n+5logn=O(n^2)
(D)2n^2+5^n=O(2^n) (E)n^7+1.5^n=O(n^7) (F)3n^2+nlog^4 n=O(nlog^4 n)
请问这题大家怎麽选?我个人觉得(D) (E) (F)都错 可是题目只要两个.....
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.39.108.200
※ 编辑: asdd 来自: 114.39.108.200 (04/01 18:53)
1F:推 koyo167:F你是不是抄错 答案可能是CE 04/01 19:03
2F:推 carterdunk:F是对的 DE错 04/01 19:08
3F:→ asdd:F怎麽看? 04/01 19:11
4F:推 carterdunk:L'Hospital rule 或取 log 都可以看出 04/01 19:15
5F:推 mhkg:F是对的 n*n < n * log n * log n * logn * logn 04/01 19:28
6F:推 cheng9115053:我觉得先确定n等级是否比(logn)^4大,(F)应该是错的 04/01 19:34
7F:→ carterdunk:F 题目是n(logn)^4 ? 04/01 19:39
8F:→ carterdunk:如果是 F是错的 04/01 19:40
9F:→ GLTY:(F)选项的确是3n^2+nlog^4 n=O(nlog^4 n) 04/01 19:43
10F:→ peterchern:我也觉得是CE 04/01 20:19
11F:推 flydragon198:我是选CE C:O(n) E:O(2^n) 不确定对不对 04/01 20:22
12F:推 carterdunk:会选C的人可能要了解O notation的涵义... 04/01 20:23
13F:→ asdd:我是选DE 04/01 20:29
14F:推 haushau:D应该对吧 都是指数时间 只是基底不同而已 04/01 20:30
15F:→ asdd:我的想法是5^n > 2^n*2^n根据定义找不到一个常数c可以满足 04/01 20:32
16F:→ asdd:c*2^n > 5^n 04/01 20:33
17F:推 leohi:想知道F+1 04/01 20:54
18F:推 mirror520:DF 04/01 21:16
19F:→ link31204:DE一票... 选C的人可能把他当西搭了吧? 04/01 21:20
20F:推 flydragon198:E一定是错的,100^7 < 1.5^7 ,应该是O(2^n) 04/01 21:20
21F:→ link31204:其实本来不管选那个错 我第二题都想写O(N^N)的 .... 04/01 21:25
22F:→ asdd:楼上 XD 你写了可能很多人会感谢你 04/01 21:27
23F:推 mirror520:1.5^n 感觉成长很小@@ 04/01 21:27
24F:→ asdd:其实 罗必达好像真的蛮好用 只是我个人不太会用@@ 04/01 21:28
25F:→ asdd:不 那是一开始 後续很可怕的!! 04/01 21:29
26F:推 flydragon198:抱歉上面打错,是1.5^100,不是1.5^7 04/01 21:29
27F:推 mirror520:XD 按了下计算机 有感觉了 感谢 04/01 21:31
28F:→ link31204:写O(N^N)一定不会错 只是怕阅卷委员觉得"假行"而已 哈 04/01 21:36
29F:→ asdd:F有没有人愿意分享一下怎样解的 04/01 23:11
30F:推 wjy123:我这样看也是觉得DEF都错耶... :( 04/01 23:27
31F:推 monkeyting:看到推文让我觉得今年有希望了... 04/02 00:14
32F:→ asdd:所以楼上是写什麽答案? 04/02 00:21
33F:→ mingrong2:(D)(F)错误!! 04/02 00:36
34F:→ mingrong2:(D)5^n>2^n,(F)n^2>nlog^4n 04/02 00:37
35F:→ mingrong2:(E)正确的原因是1.5^n趋近於1,所以等於常数 04/02 00:38
36F:→ mingrong2:n^7+常数=O(n^7) 04/02 00:39
37F:→ mingrong2:原本也差点被他骗><... 04/02 00:40
38F:推 JACKIAM:1.5的50次方就6亿多了 怎麽可能趋近於1... 04/02 00:47
39F:→ JACKIAM:只要底数大於1就不可能收敛了... 04/02 00:49
40F:→ mingrong2:对耶!!看错了= = 04/02 00:50
41F:推 leohi:楼上反串吗XDDDD 04/02 00:53
42F:推 mingrong2:那不就(D)(E)(F)都错了= = 04/02 00:54
43F:推 JACKIAM:F的话用lim (n/(logn)^4)作3次罗必达定理会趋近於0 04/02 01:02
44F:→ JACKIAM:所以(logn)^4 比 n大 04/02 01:02
45F:推 leohi:所以可以重复做路边摊定律 (笔记) 04/02 01:14
46F:推 JACKIAM:不过我刚算错了~ 後面有人PO正解 可以参考 04/02 01:17
47F:推 davchou:Big O 的定义是紧密上限,不是无限上纲吧 04/02 16:40
48F:→ asdd:根据定义没错 你甚至可以写O(n^n) 更何况他是问对错? 04/02 17:03
49F:→ asdd:当年在上洪逸的DS老师就有特别拿出来提过 分两个方向讨论 04/02 17:05
50F:→ asdd:一个是根据定义 一个是你说的紧密上限 04/02 17:07
51F:推 wjy123:我朋友说她DEF都选了 因为她怎麽看都觉得错三个... 04/02 20:58
52F:→ wjy123:题外话 她说她觉得这次她可能会败在英文跟MIS 04/02 20:59