擁抱「資料結構」的「演算法」(27) - 費式搜尋法
前言
今天要來介紹費式搜尋法，老實說我完全沒印象以前老師有教過這個，自己看了兩天才終於看懂，看起來很複雜，事實上真的很複雜XD
生活常識
你有欣賞過花朵嗎？有沒有注意到，有些花的花瓣大多是 3 瓣或 5 瓣，也有 8 瓣或 13 瓣，為什麼會這些數字這麼常出現呢？似乎是大自然的一種法則
或是某些建築例會呈現黃金比例，其實都是費氏級數的呈現
圖片來源:https://unsplash.com/photos/zHDiLstmQwo
專業知識 - 費氏級數
在介紹費式搜尋法之前，先來了解一下費氏級數或稱斐波那契數列
公式
根據公式只會用到加減運算，不需要進行乘法與除法，所以效率會比較好
數列
數列有 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...，除了最前面的兩個數值 0 與 1 之外，其他數值皆為前兩個的相加，例如 8 = 5 + 3
專業知識 - 費式搜尋法 Fibonacci Search
費式搜尋法又稱費伯那搜尋法，跟內插搜尋法一樣會透過某個公式來限縮搜尋範圍，內插搜尋法是透過斜率公式，而費式搜尋法是使用費式級數來分割，可參考維基百科的說明
費式樹
- 特性
- 費氏樹的左右子樹皆為費氏樹
- 父節點與子節點的
相差值會等於某一個費氏數值 左節點的數值會小於父節點右節點的數值會大於等於父節點
- 二元樹轉費氏樹
先將費氏級數畫成二元樹
會發現左圖的二元樹節點到F(1)就會停止，因為沒有符合 1 小於 2 了，就沒有符合 n 大於等於 2 的公式了，再將數列中的數值逐一帶入二元樹中，觀察右圖即可發現樹根的數值 = 左右節點相加的數值
資料置放的順序
存入資料數據之前，要先取得資料置放的順序，使用中序走訪費氏樹，可觀察到父節點與左右節點之間有一個固定的相差值
相差值
公式如下，其相差值為某一個費氏級數
例子
將要搜尋的資料由小至大放到費式樹中，例如，有一由小到大排列好的數列：2, 5, 17, 26, 38, 42, 59, 60, 65 ,72 ,87, 93，共 12 筆資料
- 節點數量
我們要如何知道這些數值要使用多少節點來儲存呢？可透過以下公式求得最大費氏數，其中的n為資料筆數，12 + 1 = 13，就去查表看看哪個費氏級數的數值大於或等於13，可找到F(7) = 13
- 搜尋資料
數值的搜尋要從樹根結點，樹根位置可套用公式F(a-1)，上面我們以求得 12 筆資料的最大費氏數為 F(7)，則樹根位置為 F(7-1) = F6 = 8，所以樹根在索引位置 8 的地方，然後將此位置的數值與想要找的數值相比，則可決定要繼續往左子樹還是右子樹搜尋，公式如下： - 想要找的資料
小於等於樹根節點的數值時，往左子樹找 - 想要找的資料
大於樹根節點的數值時，往右子樹找
- 步驟
假設我們想找出 26，需要執行四個步驟，詳細步驟如下：
- 尋找樹根
最大費氏數為 F(7)，則樹根位置為 F(7-1) = F6 = 8，將 26 與陣列索引 8 的數值相比，發現 26小於60，繼續往左子樹找 - 尋找
左子樹樹根
將父節點的陣列索引 8減去相差值 3 ， 8 - 3 = 5 ，將 26 與陣列索引 5 的數值相比，發現 26小於60，繼續往左子樹找 - 尋找
左子樹樹根
將父節點的陣列索引 5減去相差值 2 ， 5 - 2 = 3 ，將 26 與陣列索引 3 的數值相比，發現 26大於17，繼續往右子樹找 - 尋找
右子樹樹根
將父節點的陣列索引 3加上相差值 1 ， 3 + 1 = 4 ，將 26 與陣列索引 4 的數值相比，發現 26等於26，成功找到數值，位於陣列索引 4 的位置
分析
平均狀況下效能優於二分搜尋法，但最壞的情況下會筆二元搜尋法還慢
今日小結
費式搜尋法實作上比較複雜，還要先產生費氏樹，樹根與左右節點之間又有許多關聯，雖然是不錯的搜尋法，但實作上要考慮的事情會比較多一點，這否方便維護也是需要考量的地方，給大家參考看看囉
今日謎題
今天有一神秘數列：1, 1, 2, 3, 5, 8, 13, ...，你是不是已經猜到答案了？沒錯！就是今天內文有提到的費氏數列，但今天不是要猜費氏數列 XD
小美的數學老師提供了這段數字給班上的同學：1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, ？ ，小美一直解不出問號處的數字，你能幫助小美找到答案嗎？
昨日解題
謎題說明：練習插入的概念，選擇合適的運算符號，嘗試讓公式成立，答案為 12 + 3 - 4 x 5 + 6 = 1，你答對了嗎？
留言
張貼留言