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

看板TransCSI作者 (Let's Go Yankees)時間17年前 (2008/07/04 11:51), 編輯推噓1(1推 0噓 3→)
留言4則, 2人參與, 最新討論串1/1
假設使用快速排序法將16個數字排序 最差的情況下須要幾次比較? 答案是120次 我原本的想法是直接拿o(n^2)下去做 後來發現是錯的..... 請問各位前輩該如何解這題呢?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.127.245.213
推
07/04 19:10, , 1F
基本上那個O(n^2)還包括pivot key位置的選擇,比較次數
07/04 19:10, 1F
→
07/04 19:10, , 2F
導出來, upper-bound的T(n) = O(n^2)
07/04 19:10, 2F
→
07/04 19:11, , 3F
所以最差比較次數 " n(n-1)/2 " ,代下去
07/04 19:11, 3F
→
07/06 18:38, , 4F
Thx!!!
07/06 18:38, 4F
‣ 更多 SELAHAPPOP 的文章
文章代碼(AID): #18RPvTZv (TransCSI)