cha*_*oor 4 recursion fibonacci
众所周知，生成斐波那契数列最简单的算法如下：
if(n<=0) return 0;
else if(n==1) return 1;
f(n) = f(n-1) + f(n-2);
但该算法存在一定的重复计算。例如，如果计算 f(5)，它将计算 f(4) 和 f(3)。当您计算 f(4) 时，它将再次计算 f(3) 和 f(2)。有人能给我一个更省时的递归算法吗？
小智 5
我读过一些以高效时间复杂度计算斐波那契的方法，以下是其中一些 -
\n\n方法 1 - 动态规划\n现在这里的子结构是众所周知的，因此我将直接跳到解决方案 -
\n\nstatic int fib(int n) \n{ \nint f[] = new int[n+2]; // 1 extra to handle case, n = 0 \nint i; \n\nf[0] = 0; \nf[1] = 1; \n\nfor (i = 2; i <= n; i++) \n{ \n f[i] = f[i-1] + f[i-2]; \n} \n\nreturn f[n]; \n}\n上述空间优化版本可以按如下方式完成 -
\n\nstatic int fib(int n) \n { \n int a = 0, b = 1, c; \n if (n == 0) \n return a; \n for (int i = 2; i <= n; i++) \n { \n c = a + b; \n a = b; \n b = c; \n } \n return b; \n} \n方法 2-（使用矩阵 {{1,1},{1,0}} 的幂）
\n\n这是一个 O(n)，它依赖于这样一个事实：如果我们将矩阵 M = {{1,1},{1,0}} 与其自身相乘 n 次（换句话说，计算幂(M, n )），则我们得到第 (n+1) 个斐波那契数作为结果矩阵中行和列 (0, 0) 的元素。该解决方案的时间复杂度为 O(n)。
\n\n矩阵表示给出以下斐波那契数的闭合表达式:\nfibonaccimatrix
\n\nstatic int fib(int n) \n{ \nint F[][] = new int[][]{{1,1},{1,0}}; \nif (n == 0) \n return 0; \npower(F, n-1); \n\nreturn F[0][0]; \n} \n\n/*multiplies 2 matrices F and M of size 2*2, and \nputs the multiplication result back to F[][] */\nstatic void multiply(int F[][], int M[][]) \n{ \nint x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; \nint y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; \nint z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; \nint w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; \n\nF[0][0] = x; \nF[0][1] = y; \nF[1][0] = z; \nF[1][1] = w; \n} \n\n/*function that calculates F[][] raise to the power n and puts the \nresult in F[][]*/\nstatic void power(int F[][], int n) \n{ \nint i; \nint M[][] = new int[][]{{1,1},{1,0}}; \n\n// n - 1 times multiply the matrix to {{1,0},{0,1}} \nfor (i = 2; i <= n; i++) \n multiply(F, M); \n} \n这可以优化为 O(Logn) 时间复杂度。我们可以在前面的方法中进行递归乘法来得到power(M,n)。
\n\nstatic int fib(int n) \n{ \nint F[][] = new int[][]{{1,1},{1,0}}; \nif (n == 0) \n return 0; \npower(F, n-1); \n\nreturn F[0][0]; \n} \n\nstatic void multiply(int F[][], int M[][]) \n{ \nint x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; \nint y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; \nint z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; \nint w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; \n\nF[0][0] = x; \nF[0][1] = y; \nF[1][0] = z; \nF[1][1] = w; \n} \n\nstatic void power(int F[][], int n) \n{ \nif( n == 0 || n == 1) \n return; \nint M[][] = new int[][]{{1,1},{1,0}}; \n\npower(F, n/2); \nmultiply(F, F); \n\nif (n%2 != 0) \n multiply(F, M); \n} \n方法 3（O(log n) 时间） \n下面是一个更有趣的递推公式，可用于在 O(log n) 时间内找到第 n 个斐波那契数。
\n\n如果 n 为偶数，则 k = n/2：\nF(n) = [2*F(k-1) + F(k)]*F(k)
\n\n如果 n 是奇数，则 k = (n + 1)/2\nF(n) = F(k)*F(k) + F(k-1)*F(k-1)\n这个公式如何计算？ \n可以从上面的矩阵方程推导出公式。\nfibonaccimatrix
\n\n两边取行列式，可得\n(-1)n = Fn+1Fn-1 \xe2\x80\x93 Fn2\n此外，由于对于任意方阵 A，AnAm = An+m，因此可以导出以下恒等式：它们是从矩阵乘积的两个不同系数获得的）
\n\nFmFn + Fm-1Fn-1 = Fm+n-1
\n\n通过将 n = n+1，
\n\nFmFn+1 + Fm-1Fn = Fm+n
\n\n设 m = n
\n\nF2n-1 = Fn2 + Fn-12
\n\nF2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn （来源：Wiki）
\n\n要得到要证明的公式，我们只需执行以下操作\n如果 n 是偶数，我们可以将 k = n/2\n如果 n 是奇数，我们可以将 k = (n+1)/2
\n\npublic static int fib(int n) \n{ \n\n if (n == 0) \n return 0; \n\n if (n == 1 || n == 2) \n return (f[n] = 1); \n\n // If fib(n) is already computed \n if (f[n] != 0) \n return f[n]; \n\n int k = (n & 1) == 1? (n + 1) / 2 \n : n / 2; \n\n // Applyting above formula [See value \n // n&1 is 1 if n is odd, else 0. \n f[n] = (n & 1) == 1? (fib(k) * fib(k) + \n fib(k - 1) * fib(k - 1)) \n : (2 * fib(k - 1) + fib(k)) \n * fib(k); \n\n return f[n]; \n} \n方法 4 - 使用公式\n在此方法中，我们直接实现斐波那契数列第 n 项的公式。时间 O(1) 空间 O(1)\nFn = {[(\xe2\x88\x9a5 + 1)/2] ^ n} / \xe2\x88\x9a5
\n\nstatic int fib(int n) { \ndouble phi = (1 + Math.sqrt(5)) / 2; \nreturn (int) Math.round(Math.pow(phi, n) \n / Math.sqrt(5)); \n} \n参考：http ://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
\n