→ dendrobium:應該還是 nlogn 吧 03/25 19:30
→ luckyburgess:可以請問一下樓上大大是怎麼解的嗎@@ 03/25 20:02
推 AIdrifter:恩 對阿 我遞回式列的不知道對不對@@ 03/25 20:12
※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《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) <- 兩回合一起看
: 解開就是了..
請問一下解出來是O(n^2)嗎??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.134.213.201