Re: [理工] [DS] 98中山

看板Grad-ProbAsk作者luckyburgess (心安即自在)時間15年前 (2010/03/25 19:15)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串3/4 (看更多)

※ 引述《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

→

dendrobium

03/25 19:30, , 1^F

03/25 19:30, 1^F

→

luckyburgess

03/25 20:02, , 2^F

03/25 20:02, 2^F

推

AIdrifter

03/25 20:12, , 3^F

03/25 20:12, 3^F