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

看板Examination作者 (＊*＊ˋ(￣ ￣)時間12年前 (2013/05/13 18:56), 編輯推噓7(7推 0噓 11→)
留言18則, 7人參與, 最新討論串1/1
五、假若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
推
05/13 20:47, , 1F
2 - (0.5)^n = O(1) 因為(0.5)^n < 1
05/13 20:47, 1F
→
05/13 21:10, , 2F
喔喔 所以高上給的答案是錯的?http://tinyurl.com/c25cl83
05/13 21:10, 2F
推
05/13 21:26, , 3F
這題正確，因為O(1) =O(n)
05/13 21:26, 3F
→
05/13 21:27, , 4F
請搞清楚O notation的觀念
05/13 21:27, 4F
推
05/13 21:33, , 5F
那解答是怎麼回事@@ 有點在胡扯
05/13 21:33, 5F
→
05/13 21:40, , 6F
我的確有點迷惘 因為公職王解答又說是錯的@@
05/13 21:40, 6F
→
05/13 21:41, , 7F
05/13 21:41, 7F
推
05/13 21:41, , 8F
演算法複雜度跟程式執行次數不同 題目未講明 當然以O(n)
05/13 21:41, 8F
→
05/13 21:41, , 9F
為主
05/13 21:41, 9F
推
05/13 21:55, , 10F
O(n)是對的 是因為O-notation的定義
05/13 21:55, 10F
→
05/13 22:00, , 11F
所以應該是O(1) 但因為O(N)的成長率等級高於O(1)
05/13 22:00, 11F
→
05/13 22:00, , 12F
g(n) = O(N) 也對的意思是嗎?
05/13 22:00, 12F
推
05/13 22:05, , 13F
O(1) O(n) 都可以
05/13 22:05, 13F
→
05/13 22:06, , 14F
但我想原因不會是高上寫的那樣
05/13 22:06, 14F
→
05/13 22:13, , 15F
我有點了解了 謝謝上面各位的幫忙 :)
05/13 22:13, 15F
推
05/13 22:16, , 16F
我想是因為O(1)等級比O(n)小~依照O定義寫O(n)是對的
05/13 22:16, 16F
→
05/13 22:17, , 17F
答案要是寫O(n^2)，O(2^n)也算對
05/13 22:17, 17F
→
10/11 22:38, , 18F
10/11 22:38, 18F
‣ 更多 odj 的文章
文章代碼(AID): #1HaCR5jT (Examination)