使用合併排序法（Merge Sort）對 $n$ 個數字排序，在最佳情況（best case）及最糟情況（worst case）下，其時間複雜度（time complexity）為何？

A最佳情況：

Θ (n)

，最糟情況：

Θ (n lo g n)

B最佳情況：

Θ (n lo g n)

，最糟情況：

Θ (n lo g n)

正確答案

C最佳情況：

Θ (n)

，最糟情況：

Θ (n^{2})

D最佳情況：

Θ (n lo g n)

，最糟情況：

Θ (n^{2})

答案與詳解

正確答案

合併排序不論輸入順序皆需遞迴分割與合併,最佳與最糟皆為 Θ(n log n)。

正確。Merge Sort 的時間複雜度與輸入無關,最佳與最糟皆為 Θ(n log n)。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。

使用合併排序法（Merge Sort）對 n 個數字排序，在最佳情況（best case）及最糟情況（worst case）下，其時間複雜度（time complexity）為何？