tra*_*aww 0 algorithm performance fibonacci matrix-multiplication
如果我将使用以下方法计算Fibonacci数,它将比线性方法更快:
我对吗？
方法是从这里开始的.
DAl*_*Ale 5
式:
使用通过平方幂,你会得到一个O(log(n))乘法找到第n个斐波那契数.但是,乘法是不是在这种情况下,一个简单的操作和实际的时间复杂度为O(M(n)*log(n)),其中M(n)是一个长度为两个数字相乘的复杂性O(n).
O(log(n))
O(M(n)*log(n))
M(n)
O(n)
计算Fibonacci数的几种算法有一个基准,包括矩阵逼近和天真乘法以及Karatsuba乘法.
归档时间：
8 年，1 月 前
查看次数：
242 次
最近记录：
