IT討論區(79) 就嚟行行NPL

Fibonacci既四種寫法

原來係咁

一直都係學話要夠簡潔
原來所有野逐行逐行寫反而仲好？

如果想搵份好啲既P位
操leetcode同用udemy啲online resources以外仲有無加分位
intern exp. 已經輸在起跑線
利申有做緊 但係唔快

講緊interview個下姐，寫one line code只會令人撇不著頭腦

第五種寫法：用Binet's Formula但唔準有rounding error。

呢個係第四種

Assuming arithmetic operations are O(1) (which is not true when dealing with big-integers). There are at least 5 methods I know.

1. naive recursion, O(k^n) time and O(n) space.
2. memoizied recursion, O(n) time and space.
3. loop with 3 variables. O(n) time, O(1) space.
4. matrix multiplication, O(log n) time , O(1) space.
5. Binet's formula without rounding error. (complexity is not trivial to analyze)

For matrix multiplication, there is an optimization to use only half of the matrix but that optimization does not change the overall time complexity.

3唔計啦...只不過係2既ring buffer版
Binet做一次size estimation 決定用幾多dp 再用long integer去計 O(log n * multiplication complexity(log F(n)))?

btw log(F(n))即係n

2 & 3 are different. 2 is usually top-down where as 3 is bottom-up.

To use Binet's formula without rounding errors, one needs to deal with rational number arithmetics. That requires adding fractions, which requires computing GCD and division. I don't have a good estimate for the time complexity.

See:
https://forum.hkgolden.com/thread/6701927/page/1

我自己唔係太過覺得bottom up同top down有好大分別
唔只因為complexity一樣 仲有係可以好簡單咁轉換兩者 (with certain memory overhead which can be significant in some real life scenario)

我覺得without rounding error係只需要結果without rounding error就得 而唔駛每步概念上都0 error
所以我覺得只需要做O(log(F(n)))個dp既long fix point arithmetic 令final error <1就得
就算係中途步驟都要完全無error 留意返phi^n同pho^n都係以2^n為分母既分數 分子都係Q(sqrt(5))黎 所以其實唔需要fraction運算

Btw考慮返phi^n同pho^n用Q(sqrt(5))去計 其實已經effectively做緊recurrence relationship既計算
所以binet用黎做estimation好過真係用黎落手計

有冇巴打wfh打機
屋企好難做到野

睇住劇做