Chapter 14 搜尋法 - Ian-Liu-1990/Data-Structure GitHub Wiki

＊＊＊ 快速複習

優 點 缺 點
循序 1. 資料不用事先排序2. 適合動態資料3. 少量搜尋 Ｏ(N)，不適合N大
二分搜尋 適合大量資料Ｏ(ｌｏｇN) 1. 需要事先用陣列排好，且需要索引值，適合靜態2. 不適合動態資料
內插搜尋 適合大量且分佈平均資料，Ｏ(ｌｏｇｌｏｇN) 1. 需要事先用陣列排好，適合靜態，資料不平均退化成循序Ｏ(N)2. 不適合動態資料
雜湊法
費事搜尋 適合大量資料Ｏ(ｌｏｇN)，只依靠"加減"法 1. 需要事先用陣列排好，資料少效率差

1. 循序搜尋法

一. 循序搜尋法的適用性先決條件?

  1. 各種儲存體包含直接存取或循序存取皆可以用循序搜尋
  2. 資料不用事先排序
  3. 鏈結串列只能使用循序
  4. 若事先知道資料取用頻率，則可進行安排提高效率 <= 是否知道取用頻率(由高至低排列取用)會影響效能?
  5. 適合動態資料
  6. N很大時非常不合適

二. 循序搜尋法的搜尋時間分析

  1. Best : O(1)
  2. Worst : O(N)
  3. Avg : O(N) <= 平均比較次數 : (1 + 2 + ... N)/N = ((1+N)*N)/2N = (1+N)/2

2. 二分搜尋法

一. 二分搜尋法的適用性先決條件?

  1. 資料一定要先排序(排序演算法時間)過 : 快速排序O(NlogN)
  2. 適合靜態資料
  3. 資料必須儲存在直接存取裝置Core memory，Disk
  4. 儲存裝置必須具有隨機存取能力，如陣列，需要依索引位置跳到該位置上
  5. 適合資料量大，資料量小會因為二分搜尋法OverHead大，反而比循序時間差

二. 二分搜尋法的搜尋時間分析與二元搜尋樹無關

  1. Best : O(1)，第一次中間項極為搜尋目標
  2. Worst : O(LogN)
  3. Avg : O(LogN) = (min + max) / 2 取下限

三. ２種實現方法

  1. 陣列結構使用快速排序O(NlogN)，使用二分搜尋法O(logN)

  2. AVL-tree儲存結構O(NlogN)，使用二元搜尋樹O(logN)

3. 費式搜尋法(冷門，缺?)

一. 費式搜尋法的適用性[先決條件?]

  1. 資料一定要先排序過，需要額外陣列
  2. 適合靜態資料
  3. 不需要使用除法，只用加減法即可OverHead比二分搜尋小
  4. 適合資料量大，資料量小會OverHead大，反而比循序時間差

二. 費式搜尋法的搜尋時間分析(與二元搜尋樹無關)

  1. Avg : O(LogN)

4. 內插搜尋法

一. 內插搜尋法的適用性[先決條件?]

  1. 資料一定要先排序過，需要額外陣列
  2. 適合靜態資料
  3. 適合平均分布或分布均勻的資料進行搜尋
  4. 適合資料量大，資料量小會OverHead大，反而比循序時間差

　 I = Ｉ(low) + {（Ｉ(upper) - Ｉ(low)）（Ｋ - Ｋ(low)） / （Ｋ(upper) - Ｋ(low)）}

二. 內插搜尋法的搜尋時間分析(與二元搜尋樹無關)

  1. Avg : O(Log(LogN))，平均分布的資料，越平均效果越好，實務上幾乎為O(1)，比二分搜尋法好
  2. Worst : O(N)，資料分布不平均退化成線性搜尋

5. 雜湊法(Hashing)

I. 雜湊法原理

  1. 靜態雜湊 : 雜湊表為固定Bucket數與槽數，不會隨著資料的增加而擴張。

  2. 動態雜湊 : 雜湊表為固定Bucket數與不固定槽數，會隨著資料因發生碰撞，而增加節點擴張槽數。

II. 雜湊術語

  1. 桶子(Buckets) : 將雜湊表等分為M個桶子，每個桶子都有一個唯一的位址(或索引)，每個桶子都可以儲存若干筆資料

  2. 槽(Slots) : 將每個桶子再分為數個槽(Slots)，每個槽可以存放一筆資料

  3. 碰撞(Collision) : 不同的鍵值可能雜湊到相同的位址，有Collision並不一定有Overflow

  4. 滿溢(Overflow) : 當Collision產生，且Bucket中無多餘的Slot可存資料稱之，有Overflow，則必有Collision發生

  5. 識別字密度(計算題) : 若全部識別字或Key值共有Ｔ可能值，而當下存在雜湊表中有N筆資料，則比率Ｎ／Ｔ為識別字密度

  6. 負載密度(計算題) : 表示目前雜湊表的空間使用率，a = N/(m*s)，N目前表格中的總資料項數，m為桶子總數，s為每個桶子的槽數

  7. 完美雜湊函數 : 若任兩項資料的鍵值，以雜湊函數計算出來的位址皆不相同

III. 雜湊函數[不用管計算而是要知道特性]

  1. 中間平方法 ( Mid - square ) : 將Key平方後，取出中間某些位元來當作資料儲存位址。

  2. 折疊法 ( Folding ) : 將Key分為數段，除了最後一段外，其餘各段皆須等長，然後將每一段相加，即可得到其所對應的位址。

    • 相加的時候，有兩種方式：

      1. 位移折疊 ( Shift Folding ) : 將各段資料直接相加。

      2. 邊界折疊 ( Folding at the boundaries ) : 將奇數位段或偶數位段反轉後相加。

  3. 除法 ( Division ) : 利用Mod運算，將Key除以雜湊表的大小M(桶子的數目)，取其餘數當做索引。這個位址介於 0 ~ M-1 之間。

  4. 數字分析法 ( Digit Analysis ) : 已經事先知道會出現的Key值

    1. 觀察數字分析法：利用觀察法，將Key分佈不平均的數字刪除，其餘保留為Hash位址。

    2. 統計數字分析法：利用統計方法分析鍵值各位數的分析情形，求出Hash位址。

  5. 直接定址法：取關鍵字或關鍵字的某個線性函數值為雜湊地址。

IV. 碰撞解決或滿溢處理(Overflow Handling, Collision Resolution)

Ａ. 開放定址法 : 搜尋主要區域中開放(未被佔據)的位址並放置新記錄

  1. Linear Probing : 繼續檢查下一個Bucket直到為空Bucket，若已檢查到最後一個Bucket則循環從Table最開頭檢查;已搜尋完一圈為止，表示雜湊表滿

  2. 平方探索(Quadratic Probing) : 當碰撞而且溢位時，在雜湊表開放空間中尋找可用位置，方法是第一次碰撞位置(F(x)"＋或－"(i^2))mod m，在避免相近Key聚集，i為每次發生碰撞的次數，從i = 0(無碰撞)，i = 1(碰撞1次)...i = N(碰撞N次)次數累加

  3. 平方餘數(Quadratic Residue) : 當碰撞而且溢位時，在雜湊表開放空間中尋找可用位置，方法是第一次碰撞位置，交錯計算(F(x)+/-(i^2))mod m，在避免相近Key聚集，i為每次發生碰撞的次數，從i = 0(無碰撞)，i = 1(碰撞1次)...i = N(碰撞N次)次數累加

  4. 重複探索(Rehashing) : 前者任意排列，後者設置好一套雜湊函數，當溢位發生依序使用函數，採用另一個雜湊函式產生一個固定的增量。每隔T個位置檢查一次

  5. double hashing : 依照題目指示將值塞入雜湊表，發生碰撞再依照i為每次發生碰撞的次數，從i = 0(無碰撞)，i = 1(碰撞1次)...i = N(碰撞N次)次數累加，添加第二函數計算

Ｂ. 獨立串列(Separate Chaining) : 碰撞發生，以Link list方式串連在同一Bucket中，使每一個Bucket各自有一個鏈結新記錄

V. 雜湊碰撞特性-<相近的Key因為群聚產生的問題>?

聚集(Cluster)

  1. 線性探測產生一次聚集(primary clustering) : 任意一個落入此區間的元素都要一直探測到區間末尾，最終將加入到此區間內。導致落在區間內的關鍵字Key要多次探測才能找到合適的位置，並且還會繼續增大這個連續區間，使探測時間變得更長

  2. 平方探測的二次聚集(secondary clustering) : 解決了線性探測法的一次聚集，但是關鍵字key散列到同一位置後探測時的路徑是一樣的而且依樣拉長探測時間

  3. Open Addressing時，需注意直接或簡單的Deletion的資料位置調整:Linear Probing若簡單或直接刪除一個資料，會因為一次聚集使其他資料找不到

    • 問題 : F(x) = x mod m, 碰撞使用Linear Probing,插入39, 47, 21, 11, 7, 67, Delete 39會使67找不到

    • 解決 : "重組調整，記號法"

  4. 插入所需時間與不成功的探索的次數相同

平方探測與雙重雜湊-概念與算法