[理工] [資結]-時間複雜度

看板Grad-ProbAsk作者 (奄是涼小赫$__$)時間16年前 (2009/10/18 12:36), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 最新討論串11/38 (看更多)
T(n)=2*T(floor(n/2))+n 要證Φ(nlgn) O(nlgn) T(n) <= 2*T(n/2)+n = O(nlgn) 不知這樣是否可行? Ω(nlgn) 這要如何證呢? 現在手邊沒有書，請大家幫忙一下，感謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.210.26
推
10/18 13:33, , 1F
大概要靠數學歸納法了..
10/18 13:33, 1F
推
10/18 13:45, , 2F
T(n) = 2T(n/2)+n >= T(n/2)+n = Ω(nlgn)
10/18 13:45, 2F
→
10/20 23:55, , 3F
big O, 令T(n/2)<=c(n/2)lg(n/2), c>0
10/20 23:55, 3F
→
10/20 23:57, , 4F
T(n)<=2c(n/2)lg(n/2)+n = cnlg(n/2)+n = cnlgn-cn+n
10/20 23:57, 4F
→
10/20 23:59, , 5F
<=cnlgn, c>=1時成立, lower bound就依此類推拉
10/20 23:59, 5F
‣ 更多 sssmallwing 的文章
文章代碼(AID): #1AsfjVyg (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 38 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 sssmallwing 的文章
文章代碼(AID): #1AsfjVyg (Grad-ProbAsk)