[問題] complexity

看板Grad-ProbAsk作者 (Terry)時間16年前 (2009/04/22 02:19), 編輯推噓0(0推 0噓 8→)
留言8則, 3人參與, 最新討論串1/2 (看更多)
請教一下 T(n)約等於，T(n/2)+c,c為constant time for 乘法運算 T(n)=O(logn) 可是.. logn不是應該為1/1+1/2+...+1/n才是嗎?? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.99.191
→
04/22 09:46, , 1F
你一直遞回帶進去 最後T(n)=T(1)+clog(n)=O(log n)
04/22 09:46, 1F
→
04/22 09:50, , 2F
1/1+1/2+...+1/n這是用harmonic去夾擠所求出約等於log n
04/22 09:50, 2F
→
04/22 10:08, , 3F
T(n)=T(n/2)+c=T(n/4)+2c=.....=T(n/2^i)+ic n/2^i=1
04/22 10:08, 3F
→
04/22 10:10, , 4F
求出i=log n 代入=>T(n)=T(1)+clog n 令T(1)=0
04/22 10:10, 4F
→
04/22 10:27, , 5F
原來是這樣，謝謝您^^
04/22 10:27, 5F
→
04/22 20:52, , 6F
我覺得你對big-O的定義不太清楚，T(n) = O(logn)
04/22 20:52, 6F
→
04/22 20:53, , 7F
不代表T(n)的值等於logn，而是growth rate小於等於logn
04/22 20:53, 7F
→
04/24 23:28, , 8F
清楚了，謝謝您
04/24 23:28, 8F
‣ 更多 bernachom 的文章
文章代碼(AID): #19xWufIF (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
問題
0
8
[問題] complexity complexity
bernachom
16年前, 04/22
在新視窗開啟完整討論串 (共2篇)
‣ 更多 bernachom 的文章
文章代碼(AID): #19xWufIF (Grad-ProbAsk)