伊莉討論區

標題: 費氏搜尋法 [打印本頁]

作者: s8640920032003 時間: 2023-6-23 11:08 PM 標題: 費氏搜尋法

今天繼續來看資料結構的教學影片

這次介紹的主題是排序的演算法

頭兩個演算法我覺得還蠻直觀的

循序搜尋法就是一個一個找下去

二分搜尋法就是每次找一半一半完再切一半

但沒想到為了解決除法上的overhead

竟然有人想到了費氏搜尋法

個人覺得發明這個演算法的人還蠻厲害的

他充分利用了費氏數列F2=F1+F0的特性

把每次搜尋拆成 F(k)-1 = F(k-1)-1 +1 + F(k-2)-1

這樣就能達到跟二分搜尋法類似的效果

而且因為費氏數列的特性兩項間的差異也不會太大

不過我唯獨對費氏搜尋法有點意見的地方就是實際程式碼的原理不是這麼直觀甚至是有點繁瑣

一下要看m是不是0 一下i=F(k-1) i又變i+m i也可能變i-F(k-3)或i+F(k-3)

看了頭有點痛......

歡迎光臨伊莉討論區 (http://a401.file-static.com/)