問題詳情

46. 假設有63個數用快速排序法 (quick sort) 排序，那麼在最好的情形下要做幾次比較(比較次數最少為幾次)：
(A)62
(B)258
(C)63×62/2
(D)6

參考答案

答案：B
難度：非常困難0.166667
統計：A(16),B(14),C(19),D(24),E(0)

用户評論

【imitation】評論

這題要如何解?

【yakevinya不放手直】評論

quick sort最佳時間複雜度：O(n log n)

【hsun520】評論

最好狀況第1次循環：進行62次比較第2次循環：62/2-1=30，進行30*2=60次比較(被切成2段進行排序)第3次循環：30/2-1=14，進行14*4=56次比較(被切成4段進行排序)第4次循環：14/2-1=6，進行6*8=48次比較(被切成8段進行排序)第5次循環：6/2-1=2，進行2*16=32次比較(被切成16段進行排序)比較次數：62+60+56+48+32=258