n 代表資料筆數，則堆積排序法（Heap Sort）的時間複雜度（Time Complexity）為何？ (A) O(log n) (B) O(n) (C) O(n log n) (D) $\Omega(n^{2})$

正確答案為 C。 Heap Sort 在最佳、平均、最差情況下的時間複雜度皆為 $O(n \log n)$。 (A) $O(\log n)$ 是單次 Heapify 的成本,不是整體排序成本,錯誤。 (B) $O(n)$ 僅為建堆的成本,還要考慮 $n$ 次取出與調整,錯誤。

共 3 類科共用卷

普考-電子工程普考-電信工程普考-工業行政

計算機概要108 年第 33 題單選題

$n$ 代表資料筆數，則堆積排序法（Heap Sort）的時間複雜度（Time Complexity）為何？

O (lo g n)

O (n)

O (n lo g n)

正確答案

Ω (n^{2})

答案與詳解

正確答案

Heap Sort 在最佳、平均、最差情況下的時間複雜度皆為

O (n lo g n)

。

AO(log n)✕ 錯誤

$O(\log n)$ 是單次 Heapify 的成本,不是整體排序成本,錯誤。

BO(n)✕ 錯誤

$O(n)$ 僅為建堆的成本,還要考慮 $n$ 次取出與調整,錯誤。

CO(n log n)✓ 正確

D$\Omega(n^{2})$✕ 錯誤

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解