[問題] 快速排序法的比較問題

[SELAHAPPOP (Let's Go Yankees)]

假設使用快速排序法將16個數字排序

最差的情況下須要幾次比較?

答案是120次

我原本的想法是直接拿o(n^2)下去做 後來發現是錯的.....

請問各位前輩該如何解這題呢??

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.127.245.213
推 future1234:基本上那個O(n^2)還包括pivot key位置的選擇,比較次數
→ future1234:導出來, upper-bound的T(n) = O(n^2)
→ future1234:所以最差比較次數 " n(n-1)/2 "  ,代下去
→ SELAHAPPOP:Thx!!!