18假設在N個資料中要搜尋資料X,則對於二分搜尋(Binary search )..-阿摩線上測驗
最佳解! | ||
6F kevin huang 幼兒園下 (2019/10/27)
(B)判斷X是否在資料中的 最差情況: 在最後剩兩個數時 挑到不是X那個數(或者資料裡根本沒X) 你必須再確認 最後那個數字是否為X 所以在(Log2N)+1次比對內可以判斷出來 (D)至於時間複雜度是不管首項係數和低階項 所以最差時間複雜度還是O(log2N) |
7F 109年中華電信已錄取 高三上 (2020/03/20)
Binary search 最多搜尋:O(┌log2(n+1)┐) 最少搜尋:O(1) n+1: +1的部分是要包含剩下最後一個的那次搜尋(因為資料有可能根本不在裡面,所以剩1個也要確認) ex: 2筆資料,最多要搜尋2次 ┌ ┐:取上限的意思 |
8F
|