桶子排序(Bucket Sort)的時間複雜度在下列何種情況下達到O(n)？
A元素均勻分佈在所有桶中正確答案
B所有元素相同
C桶數量=n²
D僅一個桶
答案與詳解
為什麼答案是 A
當元素均勻分佈時，每個桶內的元素數量趨近於常數，桶內排序所需時間極小，整體時間複雜度為 O(n+k) (k為桶數)，若 k 與 n 成比例，則達到 O(n)。
考點：最佳情況考點：最壞情況考點：空間浪費考點：退化情況
載入中…
當元素均勻分佈時，每個桶內的元素數量趨近於常數，桶內排序所需時間極小，整體時間複雜度為 O(n+k) (k為桶數)，若 k 與 n 成比例，則達到 O(n)。
Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。
