計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

(B)判斷X是否在資料中的 最差情況:

在最後剩兩個數時 挑到不是X那個數(或者資料裡根本沒X)

你必須再確認 最後那個數字是否為X

所以在(Log2N)+1次比對內可以判斷出來

(D)至於時間複雜度是不管首項係數和低階項

所以最差時間複雜度還是O(log2N)

Binary search

最多搜尋:O(┌log₂⁽ⁿ⁺¹⁾┐)  

最少搜尋:O(1)

n+1: +1的部分是要包含剩下最後一個的那次搜尋(因為資料有可能根本不在裡面，所以剩1個也要確認)

ex: 2筆資料，最多要搜尋2次

┌    ┐:取上限的意思

B是錯在 "⌈log (N+1)⌉" 或者是 "⌊(logN)⌋+1" 次內才可以判斷出所要尋找的資料X是否在資料中，所以選項少算 1 次

舉個例子就知道

 ⌈log (3+1)⌉  = ⌊(log3)⌋+1 = 2 

O O O <- 三筆資料最多找 2 次 

　↑↑

    1  2

⌈log (4+1)⌉  = ⌊(log4)⌋+1 = 3

O O O O <- 四筆資料最多找 3 次

　↑↑↑
    1  2  3