題組內容

一、

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

詳解 (共 2 筆)

hchungw
hchungw
詳解 #6180373
2024/07/29
排序 n 個元素所需的最少比較次數為 Ω(nlog⁡n)，這就是比較排序演算法的理論下界。這意味著任何比較排序演算法在最壞情況下都需要至少 nlog⁡n次比較。著名的排序演算法如快速排序（Quicksort）、合併排序（Merge Sort）和堆排序（Heap Sort）都達到了這個下界。
5672
5672
詳解 #3483485
2019/07/14
至少需要n+1個比較運算，就根排列組合一...
(共 24 字，隱藏中）
前往觀看