iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 27
1
Software Development

擁抱「資料結構」的「演算法」系列 第 27

擁抱「資料結構」的「演算法」(27) - 費式搜尋法

前言

今天要來介紹費式搜尋法,老實說我完全沒印象以前老師有教過這個,自己看了兩天才終於看懂,看起來很複雜,事實上真的很複雜XD

生活常識

你有欣賞過花朵嗎?有沒有注意到,有些花的花瓣大多是 3 瓣或 5 瓣,也有 8 瓣或 13 瓣,為什麼會這些數字這麼常出現呢?似乎是大自然的一種法則
https://ithelp.ithome.com.tw/upload/images/20201010/20129841NhgmLIzyDz.png
圖片來源:https://www.pexels.com/zh-tw/photo/4621593/

或是某些建築例會呈現黃金比例,其實都是費氏級數的呈現
https://ithelp.ithome.com.tw/upload/images/20201010/20129841BQckLhSJP6.png
圖片來源:https://unsplash.com/photos/zHDiLstmQwo

專業知識 - 費氏級數

在介紹費式搜尋法之前,先來了解一下費氏級數或稱斐波那契數列

  • 公式
    根據公式只會用到加減運算,不需要進行乘法與除法,所以效率會比較好
    https://ithelp.ithome.com.tw/upload/images/20201009/20129841hZEqPIBx5D.png

  • 數列
    數列有 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...,除了最前面的兩個數值 0 與 1 之外,其他數值皆為前兩個的相加,例如 8 = 5 + 3

專業知識 - 費式搜尋法 Fibonacci Search

費式搜尋法又稱費伯那搜尋法,跟內插搜尋法一樣會透過某個公式來限縮搜尋範圍,內插搜尋法是透過斜率公式,而費式搜尋法是使用費式級數來分割,可參考維基百科的說明

費式樹

  • 特性
  1. 費氏樹的左右子樹皆為費氏樹
  2. 父節點與子節點的相差值會等於某一個費氏數值
  3. 左節點的數值會小於父節點
  4. 右節點的數值會大於等於父節點
  • 二元樹轉費氏樹
    先將費氏級數畫成二元樹
    https://ithelp.ithome.com.tw/upload/images/20201010/20129841b9Xff3l5vY.png

會發現左圖的二元樹節點到F(1)就會停止,因為沒有符合 1 小於 2 了,就沒有符合 n 大於等於 2 的公式了,再將數列中的數值逐一帶入二元樹中,觀察右圖即可發現樹根的數值 = 左右節點相加的數值
https://ithelp.ithome.com.tw/upload/images/20201010/20129841gU1oNpT5qr.png

  • 資料置放的順序
    存入資料數據之前,要先取得資料置放的順序,使用中序走訪費氏樹,可觀察到父節點左右節點之間有一個固定的相差值
    https://ithelp.ithome.com.tw/upload/images/20201010/20129841xdIJh8Mmwe.png

  • 相差值
    公式如下,其相差值為某一個費氏級數
    https://ithelp.ithome.com.tw/upload/images/20201010/20129841fAEwgKsfAs.png

例子

將要搜尋的資料由小至大放到費式樹中,例如,有一由小到大排列好的數列:2, 5, 17, 26, 38, 42, 59, 60, 65 ,72 ,87, 93,共 12 筆資料

  • 節點數量
    我們要如何知道這些數值要使用多少節點來儲存呢?可透過以下公式求得最大費氏數,其中的 n 為資料筆數,12 + 1 = 13,就去查表看看哪個費氏級數的數值大於或等於 13,可找到F(7) = 13
    https://ithelp.ithome.com.tw/upload/images/20201010/20129841JAhkDk1QWN.png

https://ithelp.ithome.com.tw/upload/images/20201010/20129841hgIZ3bJBEv.png

  • 搜尋資料
    數值的搜尋要從樹根結點,樹根位置可套用公式 F(a-1),上面我們以求得 12 筆資料的最大費氏數為 F(7),則樹根位置為 F(7-1) = F6 = 8,所以樹根在索引位置 8 的地方,然後將此位置的數值想要找的數值相比,則可決定要繼續往左子樹還是右子樹搜尋,公式如下:
  • 想要找的資料 小於等於樹根節點的數值時,往左子樹
  • 想要找的資料 大於樹根節點的數值時,往右子樹

https://ithelp.ithome.com.tw/upload/images/20201010/20129841VGp0tx5uYp.png

  • 步驟
    假設我們想找出 26,需要執行四個步驟,詳細步驟如下:
  1. 尋找樹根
    最大費氏數為 F(7),則樹根位置為 F(7-1) = F6 = 8,將 26 與陣列索引 8 的數值相比,發現 26 小於 60,繼續往左子樹
  2. 尋找左子樹樹根
    將父節點的陣列索引 8 減去相差值 3 , 8 - 3 = 5 ,將 26 與陣列索引 5 的數值相比,發現 26 小於 60,繼續往左子樹
  3. 尋找左子樹樹根
    將父節點的陣列索引 5 減去相差值 2 , 5 - 2 = 3 ,將 26 與陣列索引 3 的數值相比,發現 26 大於 17,繼續往右子樹
  4. 尋找右子樹樹根
    將父節點的陣列索引 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,你答對了嗎?


上一篇
擁抱「資料結構」的「演算法」(26) - 內插搜尋法
下一篇
擁抱「資料結構」的「演算法」(28) - 深度優先與廣度優先搜尋法
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言