請問一下!!binary search tree 的 best time,worst time,avg time,space time 各是多少?
2006-07-11 21:42:14 · 4 個解答 · 發問者 Anonymous in 電腦與網際網路 ➔ 程式設計
二元搜尋法 我想你指的是Binary Search用來尋找已排序過的List中的其中成員.
二元搜尋法的程式很短, 網上到處都可以找的到, 所以就不贅述了.
分析它的時間複雜度其實不是太難:
假設有一個已排序過的List, 有n個成員(假設為M_1, M_2, ... M_n).
第一次執行的時候, 到List中間(看要找的值x是比M_(n/2)大還是小. 如果比較小, 就去掉右邊的一半; 如果比較大, 則去掉左邊的一半. 所以你可以看出每次迴圈執行一次, List 的長度就只剩一半. 也就是說:
原來的List .... n個成員
第一次執行完 .... 剩 n/2 個成員
第二次執行完 .... 剩 n/4 個成員 == n / (2^2)
第三次執行完 .... 剩 n/8 個成員 == n / (2^3)
第四次執行完 .... 剩 n/16 個成員 == n / (2^4)
...
第k次執行完 .... 剩 n / (2^k) 個成員
迴圈終止時有三種case,
1. 目前選中的成員的值剛好是我們要的. 可以是第一次就找到(最佳情況)或是在半途就找到了(平均情況).
2. List只剩下1個成員. 而且它的的值是符合我們要找的. (最壞情況)
3. List只剩下1個成員. 但是它的的值也不是我們要找的. (最壞情況) 那我們知道要找的值不在List內.
現在我們以最糟情況來分析:
第k次執行完 .... 剩 1 個成員
之前我們已經看出List長度縮短的規律:
第k次執行完 .... 剩 n / (2^k) 個成員
所以我們可以用下列不等式(因為不等式比較general)
n / (2^k) <= 1
利用簡單的Log法則可以得到
n <= 2^k
即 k >= log2(n)
也就是O(log2 (n))
因為在Big-O內, log的底不重要, 所以可以簡化為 O(lg n).
所以我們可以確定的是這種搜尋法的時間複雜度不會糟過 O(lg n).
2006-07-16 16:31:53 · answer #1 · answered by ? 4 · 0⤊ 0⤋
這裡可以找到一堆參考資料:http://www.google.com.tw/search?num=50&hl=zh-TW&c2coff=1&q=%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6+%E4%BA%8C%E5%85%83%E6%A8%B9&meta=
2006-07-15 12:13:51 · answer #2 · answered by 憂鬱的貢丸湯 5 · 0⤊ 0⤋
就是因為找不到阿~~所以請大大能告訴我!!!感安!!!
2006-07-12 04:58:20 · answer #3 · answered by 小竹子 1 · 0⤊ 0⤋
課本有吧!?
不然,自己算算也會知道:
best time
和
worst time
連 best 和 worst 都要問,我想,真的願意回答的人不多!
2006-07-12 02:02:16 · answer #4 · answered by ? 7 · 0⤊ 0⤋