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)$。
▼ 還有更多解析內容