[理工] 資結 時間複雜度

[sssmallwing (奄是涼小赫$__$)]

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
推 FRAXIS:大概要靠數學歸納法了..
推 bennylu:T(n) = 2T(n/2)+n >= T(n/2)+n = Ω(nlgn)
→ uminchu185:big O, 令T(n/2)<=c(n/2)lg(n/2), c>0
→ uminchu185:T(n)<=2c(n/2)lg(n/2)+n = cnlg(n/2)+n = cnlgn-cn+n
→ uminchu185:<=cnlgn, c>=1時成立, lower bound就依此類推拉