close
1.循序搜尋法(sequential searching)
又稱線性搜尋法(linear search)，為一筆一筆資料依序比對，直到找到所要搜尋的記錄為止。
時間複雜度為O(n)
平均搜尋長度= ( 1 + 2 +3 + ...... + n ) / n = ( n + 1 ) / 2
2.二元搜尋法(binary searching)
取中間值與搜尋值比對
時間複雜度為O(log2n)
差的情況下， n / 2 ^ m = 1 ，m = log2n，n個串列，m次比對。
須事先予以排序
中間值：mid = ( low + high ) / 2
3.內插搜尋法(interpolation searching)
以大小資料兩端做成線性比例，再使用內插法求得所要的搜尋值。
較二元搜尋法的速度快，時間複雜度比二元搜尋法好。
有人視其為根據二元搜尋法改進的搜尋法。
mid = low + ( s - a[low] ) * (high - low ) / ( a[high] - a[low] )
low 資料範圍的下限
high 資料範圍的上限
a[low] 下限的資料
a[high] 上限的資料
s 欲搜尋的資料
例例：
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
a[7] |
a[8] |
a[9] |
a[10] | |
|
12 |
19 |
25 |
33 |
47 |
50 |
51 |
59 |
69 |
80 |
89 |
mid = 0 + ( 51 - 12 ) * ( 10 -0 ) / ( 89 - 12 ) = 39 * 10 / 77 = 5
a[5] = 50
因搜尋值為 51 大於 50 ，取大於 50 的串列。
|
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
a[7] |
a[8] |
a[9] |
a[10] |
|
|
12 |
19 |
25 |
33 |
47 |
50 |
51 |
59 |
69 |
80 |
89 |
|
|
x |
x |
x |
x |
x |
x |
|
|
|
|
|
mid = 6 + ( 51 - 51 ) * ( 10 -6 ) / ( 89 - 51 ) = 6 + 0 * 4 / 38 = 6
a[6] = 51
4.二元樹搜尋法(binary tree searching)
二元搜尋樹的定義是左子樹的鍵值小於樹根的鍵值，而右子樹的鍵值大於樹根的鍵值，針對樹根做比較。
最佳情況下的時間複雜度是O(n)，係指完整的二元樹
最差情況下的時間複雜度是O(log n)
5.平衡樹搜尋法(AVL tree searching)
每一個節點的左右子樹高度最多不超過1。
搜尋方法同二元樹搜尋法，但在搜尋前，必須先做平衡動做。
平均搜尋次數 = 搜尋次數總數 / 鍵值的個數
最大搜尋次數 = 樹的高度
全站熱搜
留言列表
電腦 (9)
