6.基數搜尋法(radix searching)
將所有鍵值以基數排序法排序完成後，將搜尋值的每一個位元做為搜尋的關鍵值，依序搜尋所要搜尋的值。
例例：
12 , 5 , 21 , 32 , 7 , 49 , 38 , 45 , 67 , 17 , 51 , 80 , 25 ，欲搜尋 38
|
基數 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 | |
|
|
鍵值 |
5 |
12 |
21 |
32 |
45 |
51 |
67 |
|
80 |
|
|
|
7 |
17 |
25 |
38 |
49 |
|
|
|
|
|
1.依十位數的基數排序。
2.將搜尋值38除以10，得3。
3.對基數3的鍵值做比較，取得38。
7.費氏級數搜尋法(Fibonacci searching)
利用費氏級數所建立的二元樹(費氏樹)來搜尋資料。
f(n) = { 1 , if n=1 or n=2
{ f( n - 1 ) + f( n - 2 ) , if n>=3
費氏數列為 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233
|
|
F7 |
|
13 |
| |||||||||
|
|
F6 |
|
8 |
| |||||||||
|
|
F5 |
|
5 |
|
11 |
| |||||||
|
|
F4 |
|
3 |
|
7 |
|
10 |
|
12 | ||||
|
|
F3 |
|
2 |
|
4 |
|
6 |
|
|
9 |
| ||
|
|
F2 |
1 |
| ||||||||||
F6 - F5 = 3 ， 3 是一個費氏數，F6共12個節點，12+1=13，13也是費氏數。
意即任一費氏樹的節點數加一，都等於費氏數(Fk)。
費氏樹包含 Fk-1 個節點的二元樹。
只用加減運算，不需用到除法運算。
平均比較次數 = ( 比較次數 * 使用頻率 ) 之總和
|
Key |
% |
|
|
|
Key |
% | ||
|
|
|
K1 |
5 |
|
|
|
K4 |
25 |
|
|
|
K2 |
10 |
|
|
|
K5 |
20 |
|
|
|
K3 |
5 |
|
|
|
K2 |
10 |
|
|
|
K4 |
25 |
|
|
|
K7 |
10 |
|
|
|
K5 |
20 |
|
=> |
|
K8 |
10 |
|
|
|
K6 |
5 |
|
|
|
K1 |
5 |
|
|
|
K7 |
10 |
|
|
|
K3 |
5 |
|
|
|
K8 |
10 |
|
|
|
K6 |
5 |
|
|
|
K9 |
5 |
|
|
|
K9 |
5 |
|
|
|
K10 |
5 |
|
|
|
K10 |
5 |
( 原始 ) ( 減少平均比較次數)
平均比較次數 = 1 * 0.05 + 2 * 0.1 + 3 * 0.05 + 4 * 0.25 + 5 * 0.2 + 6 * 0.05 + 7 * 0.1 + 8 * 0.1 + 9 * 0.05 + 10 * 0.05
= 5.15 ( 原始 )
平均比較次數 = 1 * 0.25 + 2 * 0.2 + 3 * 0.1 + 4 * 0.1 + 5 * 0.1 + 6 * 0.05 + 7 * 0.05 + 8 * 0.05 + 9 * 0.05 + 10 * 0.05
= 3.85 ( 減少平均比較次數)
全站熱搜
留言列表
電腦 (9)
