在一個有 $n$ 筆資料、依照鍵值排好序的陣列中，尋找一筆鍵值為特定數值的資料，最差情況（worst case）之時間複雜度為何？

O (1)

O (lo g n)

正確答案

O (n)

O (n lo g n)

答案與詳解

正確答案

已排序陣列可用二元搜尋,最差情況為

O (lo g n)

。

正確。已排序陣列使用二元搜尋,每次將範圍減半,最差需 $⌈ lo g_{2} n ⌉$ 次比較。

載入中…

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

在一個有 n 筆資料、依照鍵值排好序的陣列中，尋找一筆鍵值為特定數值的資料，最差情況（worst case）之時間複雜度為何？