使用合併排序法（Merge Sort）對 個數字排序，在最佳情況（best case）及最糟情況（worst case）下，其時間複雜度（time complexity）為何？
A最佳情況：，最糟情況：
B最佳情況：，最糟情況：正確答案
C最佳情況：，最糟情況：
D最佳情況：，最糟情況：
答案與詳解
逐選項解析
A最佳情況： $\Theta(n)$ ，最糟情況： $\Theta(n \log n)$✕ 錯誤
錯誤。Merge Sort 即使輸入已排序,仍需完整執行分割與合併,無法達到 Θ(n)。
B最佳情況： $\Theta(n \log n)$ ，最糟情況： $\Theta(n \log n)$✓ 正確
C最佳情況： $\Theta(n)$ ，最糟情況： $\Theta(n^{2})$✕ 錯誤
錯誤。Merge Sort 最糟為 Θ(n log n),非 Θ(n²);Θ(n²) 是 Bubble/Insertion/Selection Sort 的最糟情況。
D最佳情況： $\Theta(n \log n)$ ，最糟情況： $\Theta(n^{2})$✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
同科目歷年考卷
計算機概要 相關題目
設 n 為欲排序的數值的個數，下列關於排序演算法的敘述，何者正確？
計算機概要 · 104 年 · 第 21 題
對於排序（Sorting）的敘述，下列何者正確？
計算機概要 · 114 年 · 第 20 題
下列何者排序演算法在最差情況下（worst case）的時間複雜度最佳？
計算機概要 · 108 年 · 第 22 題
下列何者為氣泡排序法（bubble sort）在最糟情況（worst case）…
計算機概要 · 106 年 · 第 13 題
最適合做為外部排序的方法是：
計算機概要 · 106 年 · 第 4 題
用快速排序（Quick sort）來排序，並以第一個元素為基準（Pivot），下…
計算機概要 · 111 年 · 第 21 題
使用線性搜尋法（linear search）對排序過的 n 個數字陣列（arra…
計算機概要 · 107 年 · 第 22 題
關於快速排序法（quick sort）的敘述，下列何者錯誤？
計算機概要 · 109 年 · 第 22 題
