Fibonacci效能分析 on BeagleBone Black(arm-linux)
(embedded2015.hackpad.com)
從古早 PTT Java 版上找到還有另一個公式1 也是 O(log n)，但我找不到其他出處。
F0 = 0
F1 = 1
F(2n-1) = F(n)^2 + F(n-1)^2
F(2n) = (2 * F(n-1) + F(n)) * F(n)
不過有一點要注意，這複雜度是建立在數值相乘為 O(1) 的前提下，當需要用到大數時，這兩個演算法就不再是 O(log n) 了。