作者odj (***ˋ( ̄  ̄)
站内Examination
标题[考题]101普考资料处理概要
时间Mon May 13 18:56:01 2013
五、假若g(n) = 1+ (1/2) + (1/2^2 ) + … + (1/2^n-1)。 请问“g(n) = O(n)"
是否正确?为什麽?
我自己带等比级数公式算的话
g(n) = 1 - r^n / 1 - r
= 1 - (1/2)^n / (1 - 1/2)
= 1 - (1/2)^n / (1/2)
= 2 * (1 - (1/2)^n )
= 2 - 1/2^n-1
= O(1/2^n)
跟网路上看到的解答都不太一样
自己对BIG-O的算法也不是很熟,想请教一下正确答案是甚麽QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.184.130.87
1F:推 ghost00343:2 - (0.5)^n = O(1) 因为(0.5)^n < 1 05/13 20:47
3F:推 carterdunk:这题正确,因为O(1) =O(n) 05/13 21:26
4F:→ carterdunk:请搞清楚O notation的观念 05/13 21:27
5F:推 JACKIAM:那解答是怎麽回事@@ 有点在胡扯 05/13 21:33
6F:→ odj:我的确有点迷惘 因为公职王解答又说是错的@@ 05/13 21:40
8F:推 bobobola:演算法复杂度跟程式执行次数不同 题目未讲明 当然以O(n) 05/13 21:41
9F:→ bobobola:为主 05/13 21:41
10F:推 JACKIAM:O(n)是对的 是因为O-notation的定义 05/13 21:55
11F:→ odj:所以应该是O(1) 但因为O(N)的成长率等级高於O(1) 05/13 22:00
12F:→ odj:g(n) = O(N) 也对的意思是吗? 05/13 22:00
13F:推 JACKIAM:O(1) O(n) 都可以 05/13 22:05
14F:→ JACKIAM:但我想原因不会是高上写的那样 05/13 22:06
15F:→ odj:我有点了解了 谢谢上面各位的帮忙 :) 05/13 22:13
16F:推 smalldulan:我想是因为O(1)等级比O(n)小~依照O定义写O(n)是对的 05/13 22:16
17F:→ smalldulan:答案要是写O(n^2),O(2^n)也算对 05/13 22:17