回覆列表
  • 1 # 使用者6237634906850

    鄧老師的示例程式碼如下

    約定以下的敘述中用fib(n)代指斐波那契數列的第n項

    的確需要建立一個斐波那契數列備用,用到了Fib數列類建立到第lo - hi項,因為當n > 5時,fib(n) > n,肯定能夠找到不大於lo - hi的最大的斐波那契數作為mi - lo的值;當n < 5時,經驗證也能找到查詢區間的長度不一定要為斐波那契數的某一項減一。如2所說,分割的方法是找到不大於lo - hi的最大的斐波那契數作為mi - lo的值,此時有三種可能情況目標剛好是mi處的值,那麼查詢結束目標位於長度為fib(k - 1) - 1的前段, 那麼深入前段查詢,前段變成了新的查詢區間,此時查詢區間已經為某個斐波那契數減一。而且根據斐波那契數列的定義,有fib(k) - 1 = (fib(k - 1) - 1) + 1 + (fib(k - 2) - 1),即“總長 = 前段長度+ 界樁寬度 + 後段長度,且總長、前段長度、後段長度均為某個斐波那契數減一”,那麼不論目標位於何處,後續查詢中的查詢區間的長度恆為某個斐波那契數減一目標位於長度大於等於fib(k - 2) - 1的後段,那麼深入後段查詢,後段變成了新的查詢區間。此時的處理模式與之前處理得到該後段的模式相同為什麼不直接用(hi-lo)*0.618來尋找分割點?這個問題我個人的看法是乘法的開銷較大,而且對於查詢效果的提高有限。斐波那契數前後項之比 fib(n) / fib(n - 1) 也只是在n比較大的時候才接近黃金比例1.618…,而且區間的長度不一定為某個斐波那契數減一(也有可能查詢的目標是最後一個數嘛),所以斐波那契查詢的意義應該是在效果與開銷之間找到一個平衡,使效率儘可能的最大化

    個人對於演算法開銷的衡量仍處於一知半解的懵懂階段。最後一點(斐波那契查詢的優勢)如有錯誤之處,歡迎指正。

  • 中秋節和大豐收的關聯?
  • 為什麼讀《三國演義》時感覺劉備、關羽、張飛就是背上行囊、出門打工的?