測驗達人

susan
博一上
54270次
司法特考錄..
高二下
53569次
魯筱筱
研二下
44573次
(+35次)
Cyril..
研二上
38256次
(+6次)
錄事考試
小六下
25910次

公職◆資料結構題庫

【非選題】

一、給一個排序好的陣列(Sorted Array)A[low...high],當我們要搜尋一個元素 X 是否 在此陣列 A 中,二元搜尋法(Binary Search)是檢查陣列的中間位置的元素 A[next], next =,和 X 做比較,並依比較結果作下列更新。 
 Case: 
 A[next]=X:return 
 A[next]>X:high <= next-1 
A[next]<X:low <= next +1 
重複上述步驟搜尋更新的陣列 A[low...high]直到找到 X 或確認 X 不是在此陣列 A 中。 若我們設計一個新的搜尋法來修改二元搜尋法,每次都是以下列方式選取 A[next]。 next←low+ 其他步驟都和二元搜尋相同。請回答下列問題:(每小題 5 分,共 15 分)

【題組】新的搜尋法,在最差的情況下,它的執行時間複雜度為多少?原因為何?假設陣 列 A 中有 n 個元素。

#15569
編輯私有筆記