深刻分析斐波拉契数列
前言
动静布局作为一种十分经典的一类算法，不仅在解决理论问题当中有很多理论的利用，同时通常也是面试的一个重点。本篇文章一步步分析动静布局的基本原理，通过 斐波拉契数列问题 （优化工夫复杂度从 $O(2^n)$ 到O(n) 再到O(log(n))）一步一步带你从最根本的原理弄懂动静布局。咱们首先剖析斐波拉契数列问题，而后在剖析问题的时候缓缓的深刻动静布局。
斐波拉契数列
斐波拉契数列的定义如下：
$$
F_0 = 0
$$
$$
F_1 = 1
$$
$$
F_n = F_{n – 1} + F_{n- 2}
$$
就是斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。比如说在斐波拉契数列当中第一个数为 0，第二个数为 1，因而第三个数为后面两个数之和，因而第三个数为 1，同理第四个数是第二个数和第三个数之和，因而第四个数为 2，上面就是斐波拉契数的变动：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ....
斐波拉契数列——递归法
当初咱们的问题是要你求第 n 个斐波拉契数，这个问题还是比较简单的，很容易想到这就是一个能够递归解决的问题，在公式 $F_n = F_{n – 1} + F_{n-2}$ 当中也容易看出应该应用递归。当初要确定的就是递归终止条件。
- 如果
n == 0则返回 0，如果n == 1则返回 1，这就是递归终止条件。
确定完递归终止条件之后咱们很容易写出上面这样的代码：
public class Fibonacci {public static int fibonacci(int n) {if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {System.out.println(fibonacci(6));
}
}
当咱们求第 6 个斐波拉契数的时候，函数 fibonacci 的调用过程如下所示：
咱们在调用 fibonacci(6) 的时候他会调用：[fibonacci(5)和 fibonacci(4)]，而后 fibonacci(5) 会调用 [fibonacci(4) 和 fibonacci(3)]，fibonacci(4)会调用 [fibonacci(3) 和 fibonacci(2)]……
咱们容易发现咱们在函数调用的过程当中存在反复，比方下图两个雷同的局部示意对 fibonacci(4) 从新计算，因为他们的调用树都是一样的：
这种应用递归的形式计算斐波拉契数列的工夫和空间复杂度都是 $O(2^n)$。
斐波拉契数列——数组法优化工夫复杂度
既然是反复计算那么咱们是否可用防止 反复计算 呢？在计算机一种常见的做法就是 空间换工夫 ，咱们能够将之前计算的数据存下来，比方咱们用数组fib[] 存储咱们计算失去的后果，fib[i] = fibonacci(i) ，那么依据斐波拉契数列的公式咱们能够晓得：
$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$
当咱们通过数组存储两头计算的数据的时候，咱们应该应用什么样的算法进行计算呢？
在下面的图片当中比方咱们要计算 绿色框 对应的数据，依据公式：
$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$
咱们晓得 绿色框 依赖它后面的两个数据，因而咱们在计算 fib[i] 的时候，须要提前将后面两个它依赖的数据计算好，因而咱们能够从左至右计算 fib 数组，这样的话咱们在计算第 n 个fib数的时候后面 n - 1 个fib数曾经计算好了。
因而咱们的代码能够像上面这样：
public static int fibonacci(int n) {if (n <= 1)
return n;
int[] fib = new int[n + 1];
// 进行初始化操作
fib[0] = 0;
fib[1] = 1;
// 从前往后遍历失去 fib 数组的后果
for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
这种形式咱们失去的工夫和空间复杂度都降为了O(n)。
斐波拉契数列——数组法优化空间复杂度
依据下面的剖析咱们能够晓得，咱们在计算第 n 个斐波拉契数的时候仅仅依赖它后面的两个数据，因而咱们无需用一个数据将所有的数据都保留下来，咱们能够只用两个变量保留他后面的两个值即可，而后在进行 for 循环 的时候一直进行更新就行了。
public static int fibonacci(int n) {if (n <= 1)
return n;
// 进行初始化操作
int a = 0;
int b = 1;
int fib = 0;
// 从前往后遍历失去 fib 的后果
for (int i = 2; i <= n; i++) {
fib = a + b;
a = b;
b = fib;
}
return fib;
}这样咱们的工夫复杂度为 O(n) 空间复杂度就升高到了O(1)。
斐波拉契数列——矩阵乘法优化工夫复杂度
咱们曾经晓得斐波拉契数列的公式为：
$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$
$$
fib[n + 2] = fib[i + 1] + fib[i]
$$
又因为：
$$
fib[n + 1] = fib[n + 1]
$$
依据下面的公式，咱们依据矩阵乘法原理能够失去：
咱们将 n - 1 失去：
咱们不停的对上式最右侧公式进行开展能够失去
从上式看，咱们如果想求 fib[n] 的值，须要计算矩阵的幂，如果咱们间接计算的话，工夫复杂度为达到O(n)，然而咱们心愿可能将工夫复杂度升高到O(log(n))。在正式求解矩阵幂之前，咱们先思考一个问题，如何在计算 $a^n$ 时将工夫复杂度升高到O(log(n))。
疾速计算整数幂
首先咱们先明确咱们的指标：在计算 $a^n$ 时将工夫复杂度升高到O(log(n))。这个问题咱们能够间接应用一个循环就能够解决，然而工夫复杂度为O(n)：
/**
* 这个函数的目标是求解 base 的 n 次方
* @param base
* @param n
* @return
*/
public static int pow(int base, int n) {
int ans = 1;
for (int i = 0; i < n; i++)
ans *= base;
return ans;
}咱们晓得计算机在进行运算的时候都是采纳 2 进制 进行运算，所有的正整数如果是 2 的整数次幂的话，数据的二进制当中只有一个为为1，其余地位为0。
咱们晓得一个数据用二进制示意只有某些地位为 0，某些地位为 1，那么一个整数肯定能够用若干个整数相加失去，而且这些整数满足 2 的整数次幂，比方下图中的7 = 1 + 2 + 4：
同样的咱们须要求解的 $2^n$ 上的 n 也是能够通过加法失去，比如说 $2^7 = 2^1 * 2^2 * 2^4 = 2^{(1 + 2 + 4)}$，因而咱们能够应用上面的代码进行疾速幂的求解：
/**
* 这个函数的目标是求解 base 的 n 次方
* @param base
* @param n
* @return
*/
public static int power(int base, int n) {if (n == 0) return 1;
int ans = 1;
for (int i = 0; i < n; i++) {
// 这个右移的目标是查看 n 第 i 个比特地位上是否为 1 如果为 1 就须要进行乘法运算
// 这就相当于 ans *= base^i
if (((n >> i) & 1) == 1) {ans *= base; // 这就相当于 幂相加 能够仔细分析下面的 2^7 的运算形式}
// base 的变动状况为 base^1, base^2, base^3, base^4, ...
// 比如说当 base 为 2 时，base 的变动状况为 1, 2, 4, 8, 16, 32, 64, ...
base *= base;
}
return ans;
}
斐波拉契数据列矩阵乘法的疾速幂
首先在咱们计算当中须要进行一个 2x2 的矩阵乘法运算，首先咱们先定义一个简略的 2x2 矩阵乘法运算。
/**
* 这里为了简略期间，因为咱们的矩阵乘法是 2x2 的
* 所以能够间接做这样的简略的乘法
* @param a
* @param b
* @return
*/
public static int[][] matrixMultiply(int[][] a, int[][] b) {int[][] ans = new int[2][2];
ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
return ans;
}
咱们当初来看咱们应用矩阵疾速幂失去斐波拉契数列的后果：
public static int fibonacci(int n) {if (n <= 1) return n;
// 这个函数的作用是失去后面提到的矩阵的 n 次幂的后果
int[][] mm = fibMatrixPower(n); // 这个函数的具体实现在上面
// 依据下图当中的公式容易晓得咱们最终返回的后果就是 mm[1][0] 因为 fib[1] = 1 fib[0] = 0
return mm[1][0];
}public static int[][] fibMatrixPower(int n) {
// 这个矩阵是依据上图咱们的公式失去的
int[][] baseMatrix = {{1, 1}, {1, 0}};
if (n == 1)
return baseMatrix;
// 初始化为单位矩阵 如果是整数幂 初始化为 1
// 这里初始化为单位矩阵的目标是因为单位矩阵和任何矩阵
// 相乘后果都为原矩阵
int[][] ans = {{1, 0}, {0, 1}};
for (int i = 0; i < n; i++) {
// 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行矩阵乘法运算
if (((n >> i) & 1) == 1) {
// 进行矩阵乘法运算 相当于整数幂的时候数值乘法
ans = matrixMultiply(ans, baseMatrix);
}
// 进行矩阵乘法运算求矩阵频发 相当于整数幂的时候数值乘法 求数值的平方
baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
}
return ans;
}
以上就是本文对于求解斐波拉契数列的各种办法，残缺代码如下：
public class Fibonacci {public static int fibonacci1(int n) {if (n <= 1)
return n;
return fibonacci1(n - 1) + fibonacci1(n - 2);
}
public static int fibonacci2(int n) {if (n <= 1)
return n;
int[] fib = new int[n + 1];
// 进行初始化操作
fib[0] = 0;
fib[1] = 1;
// 从前往后遍历失去 fib 数组的后果
for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
public static int fibonacci3(int n) {if (n <= 1)
return n;
// 进行初始化操作
int a = 0;
int b = 1;
int fib = 0;
// 从前往后遍历失去 fib 的后果
for (int i = 2; i <= n; i++) {
fib = a + b;
a = b;
b = fib;
}
return fib;
}
/**
* 这个函数的目标是求解 base 的 n 次方
* @param base
* @param n
* @return
*/
public static int power(int base, int n) {if (n == 0) return 1;
int ans = 1;
for (int i = 0; i < n; i++) {
// 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行乘法运算
// 这就相当于 ans *= base^i
if (((n >> i) & 1) == 1) {ans *= base;}
// base 的变动状况为 base^1 base^2 base^3 ...
// 比如说当 base 为 2 时，base 的变动状况为 1, 2, 4, 8, 16, 32, 64, ...
base *= base;
}
return ans;
}
public static int pow(int base, int n) {
int ans = 1;
for (int i = 0; i < n; i++)
ans *= base;
return ans;
}
/**
* 这里为了简略期间，因为咱们的矩阵乘法是 2x2 的
* 所以能够间接做这样的简略的乘法
* @param a
* @param b
* @return
*/
public static int[][] matrixMultiply(int[][] a, int[][] b) {int[][] ans = new int[2][2];
ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
return ans;
}
public static int[][] fibMatrixPower(int n) {int[][] baseMatrix = {{1, 1}, {1, 0}};
if (n == 1)
return baseMatrix;
// 初始化为单位矩阵 如果是整数幂 初始化为 1
int[][] ans = {{1, 0}, {0, 1}};
for (int i = 0; i < n; i++) {
// 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行矩阵乘法运算
if (((n >> i) & 1) == 1) {ans = matrixMultiply(ans, baseMatrix);
}
baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
}
return ans;
}
public static int fibonacci(int n) {if (n <= 1) return n;
int[][] mm = fibMatrixPower(n);
return mm[1][0];
}
public static void main(String[] args) {System.out.println(fibonacci1(1));
// System.out.println(power(2, 8));
// System.out.println(power(2, 8));
System.out.println(fibonacci(1));
}
}总结
咱们当初来从新捋一下咱们在下面学习斐波拉契数列的思路：
首先咱们用于解决斐波拉契数列的办法是 递归法 然而这个办法有一个很大的问题，就是计算某个斐波拉契数的时候它依赖于它后面的斐波拉契数（这个过程相当于将一个大问题划分成若干个小问题），这个依赖会导致咱们进行很多反复的运算，为了解决这个问题咱们用到了 数组法，这其实就是一个用空间换工夫的办法，用数组将后面计算你的后果存储下来，防止反复计算。
通过剖析咱们公式，咱们发现咱们的数据依赖关系，咱们在计算某个斐波拉契数的时候只须要依赖它后面的两个斐波拉契数，因而咱们不必存储咱们计算的每一个斐波拉契数，只须要保留两个值即可，这就是咱们 优化数组法 的原理。
最初咱们通过 疾速矩阵幂 的办法将咱们的工夫复杂度从 O(n) 升高到了O(long(n))，这个办法其实带有肯定的技巧性，在大多数动静布局的算法当中咱们用不到它，也就是说它的普适性并不强。
从下面的剖析咱们能够总结咱们在应用动静布局时的大抵思路：
- 将大问题划分成小问题，小问题持续划分 ……，学术一点的话说就是重叠子问题。
- 是否存在反复计算，如果存在应用空间换工夫的办法进行优化，这是动静布局一个十分重要的点。
- 是否可能对数组的空间复杂度进行优化。
在本篇文章当中次要和大家一起从 0 开始分析斐波拉契数列问题，有几个优化过程，整体的内容还是比拟多的，心愿大家有所播种，我是 LeHung，咱们下期再见！！！（记得 点赞 珍藏哦！）
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。