[考題]101普考資料處理概要

五、假若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 -- ◆ From: 111.184.130.87
※ 批踢踢實業坊(ptt.cc)
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1368442565.A.B5D.html

推 ghost00343:2 - (0.5)^n = O(1) 因為(0.5)^n < 1 05/13 20:47

→ odj:喔喔 所以高上給的答案是錯的?http://tinyurl.com/c25cl83 05/13 21:10

推 carterdunk:這題正確，因為O(1) =O(n) 05/13 21:26

→ carterdunk:請搞清楚O notation的觀念 05/13 21:27

推 JACKIAM:那解答是怎麼回事@@ 有點在胡扯 05/13 21:33

→ odj:我的確有點迷惘 因為公職王解答又說是錯的@@ 05/13 21:40

→ odj:http://tinyurl.com/cqnjexy 05/13 21:41

推 bobobola:演算法複雜度跟程式執行次數不同 題目未講明 當然以O(n) 05/13 21:41

→ bobobola:為主 05/13 21:41

推 JACKIAM:O(n)是對的 是因為O-notation的定義 05/13 21:55

→ odj:所以應該是O(1) 但因為O(N)的成長率等級高於O(1) 05/13 22:00

→ odj:g(n) = O(N) 也對的意思是嗎? 05/13 22:00

推 JACKIAM:O(1) O(n) 都可以 05/13 22:05

→ JACKIAM:但我想原因不會是高上寫的那樣 05/13 22:06

→ odj:我有點了解了 謝謝上面各位的幫忙 :) 05/13 22:13

推 smalldulan:我想是因為O(1)等級比O(n)小~依照O定義寫O(n)是對的 05/13 22:16

→ smalldulan:答案要是寫O(n^2)，O(2^n)也算對 05/13 22:17

→ sneak: ) https://daxiv.com 10/11 22:38