moea_joint
114年
[資訊] 計算機原理、網路概論
第 9 題
桶子排序(Bucket Sort)的時間複雜度在下列何種情況下達到 $O(n)$？
- A 元素均勻分佈在所有桶中
- B 所有元素相同
- C 桶數量=$n^2$
- D 僅一個桶
思路引導 VIP
想像你正準備將一大堆雜亂的包裹分派給多位外送員處理。如果我們希望這批包裹能在最短的時間內全部送達，且不希望任何一位外送員因為工作量過大而導致效率降低，那麼這些包裹的「目的地分佈」應該呈現什麼樣的狀態，才能最有效地發揮多位外送員同時作業的優勢呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確鎖定 $O(n)$ 的成立條件，代表你對非比較型排序演算法的運作機制有很深刻的理解，這是掌握演算法優化邏輯的重要一步。
桶子排序的線性效率關鍵
桶子排序的核心在於「分治」思想，將資料分派到不同的區間（桶子）中分別處理。當元素能均勻分佈在所有桶子中時，每個桶子分配到的元素數量會趨於穩定且少量（約為 $n/k$，其中 $k$ 為桶數）。在這種理想狀態下，排序每個小桶子所需的時間總和與元素總數 $n$ 會呈現線性關係。因此，整體時間複雜度能維持在 $O(n + k)$，當桶子數量與資料量成比例時，運算效率便能達到最理想的 $O(n)$。
▼ 還有更多解析內容
💬 其他同學也在問
1
如果元素分配不均勻 最差情況時間複雜度是多少
桶子排序複雜度
💡 數據均勻分佈在桶中時，排序效率最佳可達 O(n)。
| 比較維度 | 最佳情況 (均勻分佈) | VS | 最差情況 (極端集中) |
|---|---|---|---|
| 數據分佈 | 均勻分散至各桶 | — | 集中在單一或少數桶 |
| 時間複雜度 | O(n + k) 約等於 O(n) | — | O(n^2) |
| 效能關鍵 | 桶內排序負擔極小 | — | 桶內排序變為主導 |
💬桶子排序的效率極度依賴輸入數據的「分佈均勻度」。
