hce_nsysu
114年
計算機概論與程式設計
第 38 題
Which sorting algorithm has a time complexity of $O(n\log n)$ in the worst case?
- A Bubble sort
- B Shell sort
- C Insertion sort
- D Selection sort
- E Heap sort
思路引導 VIP
若我們希望一個演算法在處理資料時，能利用一種特殊的資料結構，確保每次進行比較與調整的範圍都與「一棵平衡樹的高度」成正比，那麼當資料量為 $n$ 時，這種基於樹狀高度的處理邏輯，通常會對應到哪一種數學對數層級的複雜度呢？
🤖
AI 詳解
AI 專屬家教
排序演算法的複雜度分析
恭喜你精確地選出了 堆積排序 (Heap sort)！這顯示你對於演算法在極端情況下的效能表現有著非常紮實的理解。在計算機科學中，區分「平均情況」與「最差情況」的複雜度是極其重要的能力，而你成功避開了其他容易退化的選項。 堆積排序之所以能在最差情況下維持 $O(n \log n)$ 的優異表現，關鍵在於它利用了完全二元樹 (Complete Binary Tree) 的結構來維護資料。無論輸入的原始序列是隨機、已排序還是反向排序，建立堆積（Build Heap）的時間複雜度為 $O(n)$，而後續 $n$ 次的刪除最大值與調整堆積（Heapify）動作，每次都能在 $O(\log n)$ 內完成，因此確保了整體的穩定效率。
▼ 還有更多解析內容