申論題 - 阿摩線上測驗

申論題資訊

試卷：104年 - 104 專技高考_電子工程技師：電子計算機原理#41860
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：104年
排序：0

一、

⑴任何使用比較運算（comparison）的排序演算法，當其輸入的資料項目的數目為 n 時，最少需要多少個比較運算方能完成？請使用時間複雜度表示之，並說明其理由。（10 分）

詳解提供者：hchungw

排序 n 個元素所需的最少比較次數為 Ω(nlog⁡n)，這就是比較排序演算法的理論下界。這意味著任何比較排序演算法在最壞情況下都需要至少 nlog⁡n次比較。著名的排序演算法如快速排序（Quicksort）、合併排序（Merge Sort）和堆排序（Heap Sort）都達到了這個下界。