Re: [理工] [DS] 98中山
※ 引述《luckyburgess (心安即自在)》之銘言：
: ※ 引述《FRAXIS (喔喔)》之銘言：
: : 他是說，假設上一回合選到最差的，那這一回合就會選到最好的情況下複雜度是多少。
: : 以Quicksort來說，就是一回合會分的極不平均，下一回合會剛好切半。
: : 所以就可以得到遞迴關係式
: : T(n) = T(n-1) + T(1) + O(n) <- 第一回合
: : = T(n-1/2) + T(n-1/2) + T(1) + O(n) <- 兩回合一起看
: : 解開就是了..
: 請問一下解出來是O(n^2)嗎??
n-1 n
T(n) = 2T( ----- ) + cn 小於等於 2T( --- ) + cn = O(nlogn)
2 2
因此 T(n) = O(nlogn)
--
人家可不是為了你才這樣做的哦!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.198.35.85
推
03/25 22:18, , 1F
03/25 22:18, 1F
討論串 (同標題文章)