Re: [理工] [DS] 98中山
※ 引述《swda078285 (挖哈哈)》之銘言：
: 還有第6題
: 剛有爬文
: 是說利用middle of three來計算他平均複雜度嗎？
他是說，假設上一回合選到最差的，那這一回合就會選到最好的情況下複雜度是多少。
以Quicksort來說，就是一回合會分的極不平均，下一回合會剛好切半。
所以就可以得到遞迴關係式
T(n) = T(n-1) + T(1) + O(n) <- 第一回合
= T(n-1/2) + T(n-1/2) + T(1) + O(n) <- 兩回合一起看
解開就是了..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
討論串 (同標題文章)