斐波那契数列最优解法（斐波那契数列最优解-矩阵快速幂）
斐波那契数列最优解法（斐波那契数列最优解-矩阵快速幂）4、矩阵快速幂public static long f3(int n) { double result = 0; double temp = Math.sqrt(5.0); result = (Math.pow((1 temp) / 2 n) - Math.pow((1 - temp) / 2 n)) / temp; return (long) result; }时间复杂度依赖于java计算方式。但是由于计算机精度问题，导致该方式在n=71之后就不再准确。public static long f2(int n) { if (n <= 0) { throw new RuntimeException("输入参数小于1"); }
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1 F(n)=F(n - 1) F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。
1、递归
public static long f1(int n long[] f) {
if (n < 1) {
throw new RuntimeException("输入参数小于1");
}
if (n == 1 || n == 2) {
return 1;
}
if (f[n] == 0) {
f[n] = f1(n-1 f) f1(n-2 f);
}
return f[n];
}
递归比较直观，但是由于是逆推，重复计算，所以效率低下，可加入map对象查找进行优化，但是由于递归的本质，会导致栈溢出风险，不推荐。
2、顺序加
public static long f2(int n) {
if (n <= 0) {
throw new RuntimeException("输入参数小于1");
}
if (n == 1 || n == 2) {
return 1;
}
long a = 1;
long b = 1;
long c = 0;
for (int i = 3; i <= n; i ) {
c = a b;
a = b;
b = c;
}
return c;
}
无递归栈溢出风险，效率高，时间复杂度O(n).
3、数学表达式计算
通过数学推导，可得出如下结论：
public static long f3(int n) {
double result = 0;
double temp = Math.sqrt(5.0);
result = (Math.pow((1 temp) / 2 n) - Math.pow((1 - temp) / 2 n)) / temp;
return (long) result;
}
时间复杂度依赖于java计算方式。但是由于计算机精度问题，导致该方式在n=71之后就不再准确。
4、矩阵快速幂
public static long f4(int n){
if (n <= 0) {
throw new RuntimeException("输入参数小于1");
}
if (n == 1 || n == 2) {
return 1;
}
//单位矩阵
long[][] result = {{1} {0}};
long[][] tem = {{1 1} {1 0}};
while (n != 0) {
if ((n & 1) == 1) {
result = matrixMultiply(tem result);
}
tem = matrixMultiply(tem tem);
//右移一位并赋值
n >>= 1;
}
return result[1][0];
}
两个矩阵的乘法：（矩阵相乘方法：http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html）
/*矩阵乘法*/
private static long[][] matrixMultiply(long[][] a long[][] b){
int rows = a.length;
int cols = b[0].length;
long[][] matrix = new long[rows][cols];
for (int i = 0; i < a.length; i ) {
for (int j = 0; j < b[0].length; j ) {
for (int k = 0; k < a[i].length; k ) {
matrix[i][j] = a[i][k] * b[k][j];
}
}
}
return matrix;
}
虽然matrixMultiply方法中为for循环嵌套，但是由于斐波那契数列为2*2矩阵，其循环次数一定，时间复杂度可看为O(1) 故矩阵快速幂方式求解斐波那契数列时间复杂度为O(logn)。
