作者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