作者sssmallwing (奄是凉小赫$__$)
看板Grad-ProbAsk
标题[理工] 资结 时间复杂度
时间Sun Oct 18 12:36:45 2009
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
1F：推 FRAXIS:大概要靠数学归纳法了.. 10/18 13:33
2F：推 bennylu:T(n) = 2T(n/2)+n >= T(n/2)+n = Ω(nlgn) 10/18 13:45
3F：→ uminchu185:big O, 令T(n/2)<=c(n/2)lg(n/2), c>0 10/20 23:55
4F：→ uminchu185:T(n)<=2c(n/2)lg(n/2)+n = cnlg(n/2)+n = cnlgn-cn+n 10/20 23:57
5F：→ uminchu185:<=cnlgn, c>=1时成立, lower bound就依此类推拉 10/20 23:59