3
Fibonacci效能分析 on BeagleBone Black(arm-linux) (embedded2015.hackpad.com)
sayuan 積分 1 編輯於

從古早 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) 了。

Blake 積分 1

原來還有O(log n)的解法…滿神的…

面試如果這樣寫…不知道會不會被說錯XDDDDD