java斐波那契优化,[LintCode]斐波纳契数列实现及优化

素颜马尾好姑娘i 2023-01-13 10:11 103阅读 0赞

由于简书不支持 Latex ，建议去我的博客看原文：斐波纳契数列实现及优化

求关注、求交流、求意见、求建议。

前言

LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。

题目

LintCode：斐波纳契数列

描述

查找 斐波纳契数列 中第 N 个数。

所谓的 斐波纳契数列 是指：

前两个数是 0 和 1 。

第 i 个数是第 i-1 个数和第 i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例

给定 1，返回 0

给定 2，返回 1

给定 10，返回 34

实现

递归实现

问题分析

根据 斐波那契数列 的定义得：

\\begin\{aligned\}

f(1) & = 0\\

f(2) & = 1\\

f(n) & = f(n - 1) + f(n - 2)\\qquad n\\in\{3,4,5\\ldots\}

\\end\{aligned\}

根据上述表达式最明显的实现方式便是递归。

实现 - C++

class Solution\{

public:

int fibonacci(int n) \{

if (n == 1) \{

return 0;

\} else if (n == 2) \{

return 1;

\} else \{

return fibonacci(n - 1) + fibonacci(n - 2);

\};

实现 - Java

class Solution \{

public int fibonacci(int n) \{

if (n == 1) \{

return 0;

\} else if (n == 2) \{

return 1;

\} else \{

return fibonacci(n - 1) + fibonacci(n - 2);

结果分析

结果：结果不尽人意，速度非常慢，甚至没有通过 LintCode 的评测。

分析：这种递归不同于一般的递归，在 n 较大时，两次递归调用中存在大量的重复运算，导致速度非常慢。

非递归实现

问题分析

在递归实现中，由于大量的重复运算导致速度慢，所以采用非递归形式，思路也非常简单：从 f(0) 开始根据公式叠加至 f(n) 。

实现 - C++

class Solution\{

public int fibonacci(int n) \{

if (n == 1) \{

return 0;

\} else if (n == 2) \{

return 1;

\} else \{

int n1 = 0;

int n2 = 1;

int sn = 0;

while (n > 2) \{

sn = n1 + n2;

n1 = n2;

n2 = sn;

n--;

return sn;

\};

实现 - Java

class Solution\{

public:

int fibonacci(int n) \{

if (n == 1) \{

return 0;

\} else if (n == 2) \{

return 1;

\} else \{

int n1 = 0;

int n2 = 1;

int sn = 0;

while (n > 2) \{

sn = n1 + n2;

n1 = n2;

n2 = sn;

n--;

return sn;

\};

结果分析

结果：经测试 C++ 最快可以以 10ms 轻松通过 LintCode 的评测。

分析：时间复杂度为 o(n) ，空间复杂度为 o(1) ，效果不错。

细节：使用 while 代替 for 节省了一个 Int(4Byte) 的空间。

递归实现优化

问题分析

类似的递归重复计算问题很多，但未必都可以简单的像 斐波那契数列 问题这么容易化为非递归，那么有没有办法递归的前提下保证没有重复计算呢？思路也很简单：计算结果加入缓存。

实现 - C++

class Solution\{

public:

vector buffer;

int fibonacci(int n) \{

if(n == 1)\{

return 0;

\} else if (n == 2)\{

return 1;

int n1, n2, sn;

if (buffer.size() == 0) \{

buffer.push\_back(0);

buffer.push\_back(1);

if (buffer.size() > n - 2) \{

n1 = buffer\[n - 2\];

\} else \{

n1 = fibonacci(n - 1);

if (buffer.size() > n - 3) \{

n2 = buffer\[n - 3\];

\} else \{

n2 = fibonacci(n - 2);

sn = n1 + n2;

if (buffer.size() < n) \{

buffer.push\_back(sn);

return sn;

\};

实现 - Java

class Solution \{

ArrayList buffer = new ArrayList();

public int fibonacci(int n) \{

if(n == 1)\{

return 0;

\} else if (n == 2)\{

return 1;

int n1, n2, sn;

if (buffer.size() == 0) \{

buffer.add(0);

buffer.add(1);

if (buffer.size() > n - 2) \{

n1 = buffer.get(n - 2);

\} else \{

n1 = fibonacci(n - 1);

if (buffer.size() > n - 3) \{

n2 = buffer.get(n - 3);

\} else \{

n2 = fibonacci(n - 2);

sn = n1 + n2;

if (buffer.size() < n) \{

buffer.add(sn);

return sn;

结果分析

结果：经测试 C++ 同样最快可以以 10ms 轻松通过 LintCode 的评测。 Java 也跑出了 1269ms 的成绩，可喜可贺。

分析：虽然空间复杂度相对非递归提升到了 o(n) ，不过在不改动递归结构的前提下，也算达到了不错的效果。

细节：

在枚举 f(1) 、 f(2) 后再声明变量，以节约内存空间。

n 是从 1 开始，buffer 是从 0 开始。

f(1) 和 f(2) 要一开始加进来，如果递归加入会顺序相反，导致结果出错。

矩阵快速幂实现

概述

根据@iFzzzh的提醒，发现了大大降低时间复杂度的方法。

原理

先介绍一下什么是快速幂，如下式：

f(n) = a^n\\tag\{1\}

当 $n$ 为偶数时则有:

f(n) = (a\{\\frac\{n\}\{2\}\})2=f(\\frac\{n\}\{2\})^2\\tag\{2\}

当 $n$ 为奇数时则有:

f(n) = (a\{\\lfloor\\frac\{n\}\{2\}\\rfloor\})2 \\times a=f(\\lfloor\\frac\{n\}\{2\}\\rfloor)^2\\times a\\tag\{3\}

显然 (1) 式时间复杂度为 o(n) ，而 (2) (3) 式复杂度为 o(log\_2 n)，这就是快速幂，简单的来说就是以二分降幂的方式减少计算步骤。

问题分析

类比上述的快速幂法，采用矩阵的方式也可以将 斐波那契数列 化为 a^n 的格式，达到降幂的效果：

\\begin\{aligned\}

\\begin\{bmatrix\}

f(n)\\

f(n-1)\\

\\end\{bmatrix\}&=

\\begin\{bmatrix\}

f(n-1)+f(n-2)\\

f(n-1)\\

\\end\{bmatrix\}\\\\

&=\\begin\{bmatrix\}

1 & 1\\

1 & 0\\

\\end\{bmatrix\}\\times

\\begin\{bmatrix\}

f(n-1)\\

f(n-2)\\

\\end\{bmatrix\}\\\\

&=\\begin\{bmatrix\}

1 & 1\\

1 & 0\\

\\end\{bmatrix\}^2\\times

\\begin\{bmatrix\}

f(n-2)\\

f(n-3)\\

\\end\{bmatrix\}\\

&\\qquad\\qquad\\quad\\vdots\\

&=\\begin\{bmatrix\}

1 & 1\\

1 & 0\\

\\end\{bmatrix\}^\{n-2\}\\times

\\begin\{bmatrix\}

f(2)\\

f(1)\\

\\end\{bmatrix\}\\

\\end\{aligned\}

根据 斐波那契数列 的定义，f(1) f(2) 为常数，此时便可以通过快速幂的方式计算 f(n) 的值了。

实现 - C++

class Solution\{

public:

int fibonacci(int n) \{

if(n == 1)\{

return 0;

if(n == 2)\{

return 1;

int s\[2\]\[2\];

rxn(n - 2, s);

return s\[0\]\[0\];

void rxn(int n, int result\[2\]\[2\])\{

if(n == 0)\{

result\[0\]\[0\] = 1;

result\[0\]\[1\] = 0;

result\[1\]\[0\] = 0;

result\[1\]\[1\] = 1;

return;

if(n == 1)\{

result\[0\]\[0\] = 1;

result\[0\]\[1\] = 1;

result\[1\]\[0\] = 1;

result\[1\]\[1\] = 0;

return;

if(n > 1)\{

int s\[2\]\[2\] = \{1, 1, 1, 0\};

int buffer\[2\]\[2\];

rxn(n / 2, buffer);

int buffer2\[2\]\[2\];

mul(buffer, buffer, buffer2);

if(n % 2 == 0)\{

result\[0\]\[0\] = buffer2\[0\]\[0\];

result\[0\]\[1\] = buffer2\[0\]\[1\];

result\[1\]\[0\] = buffer2\[1\]\[0\];

result\[1\]\[1\] = buffer2\[1\]\[1\];

\}else\{

mul(buffer2, s, result);

void mul(int m1\[2\]\[2\], int m2\[2\]\[2\], int result\[2\]\[2\]) \{

result\[0\]\[0\] = m1\[0\]\[0\] \* m2\[0\]\[0\] + m1\[0\]\[1\] \* m2\[1\]\[0\];

result\[0\]\[1\] = m1\[0\]\[0\] \* m2\[0\]\[1\] + m1\[0\]\[1\] \* m2\[1\]\[1\];

result\[1\]\[0\] = m1\[1\]\[0\] \* m2\[0\]\[0\] + m1\[1\]\[1\] \* m2\[1\]\[0\];

result\[1\]\[1\] = m1\[1\]\[0\] \* m2\[0\]\[1\] + m1\[1\]\[1\] \* m2\[1\]\[1\];

\};

实现 - Java

class Solution \{

public int fibonacci(int n) \{

if(n == 1)\{

return 0;

\} else if (n == 2)\{

return 1;

int s\[\]\[\] = new int\[2\]\[2\];

rxn(n - 2, s);

return s\[0\]\[0\];

public void rxn(int n, int\[\]\[\] result)\{

if(n == 0)\{

result\[0\]\[0\] = 1;

result\[0\]\[1\] = 0;

result\[1\]\[0\] = 0;

result\[1\]\[1\] = 1;

return;

if(n == 1)\{

result\[0\]\[0\] = 1;

result\[0\]\[1\] = 1;

result\[1\]\[0\] = 1;

result\[1\]\[1\] = 0;

return;

if(n > 1)\{

int s\[\]\[\] = \{ \{1, 1\}, \{1, 0\}\};

int buffer\[\]\[\] = new int\[2\]\[2\];

rxn(n / 2, buffer);

int buffer2\[\]\[\] = new int\[2\]\[2\];

mul(buffer, buffer, buffer2);

if(n % 2 == 0)\{

result\[0\]\[0\] = buffer2\[0\]\[0\];

result\[0\]\[1\] = buffer2\[0\]\[1\];

result\[1\]\[0\] = buffer2\[1\]\[0\];

result\[1\]\[1\] = buffer2\[1\]\[1\];

\}else\{

mul(buffer2, s, result);

public void mul(int\[\]\[\] m1, int\[\]\[\] m2, int\[\]\[\] result) \{

result\[0\]\[0\] = m1\[0\]\[0\] \* m2\[0\]\[0\] + m1\[0\]\[1\] \* m2\[1\]\[0\];

result\[0\]\[1\] = m1\[0\]\[0\] \* m2\[0\]\[1\] + m1\[0\]\[1\] \* m2\[1\]\[1\];

result\[1\]\[0\] = m1\[1\]\[0\] \* m2\[0\]\[0\] + m1\[1\]\[1\] \* m2\[1\]\[0\];

result\[1\]\[1\] = m1\[1\]\[0\] \* m2\[0\]\[1\] + m1\[1\]\[1\] \* m2\[1\]\[1\];

结果分析

结果：C++ 最快可以以 10ms 通过 LintCode 的评测。 Java 最快可以以 1200ms 通过 LintCode 的评测。

分析：可能是由于 LintCode 测试数据不够大的原因，矩阵快速幂并没有体现出时间复杂度为 o(log\_2 n) 应有的优势，不过根据其单步计算量提升，时间却与 非递归 递归优化 达到同一水平，可以判断出其效果还是有的。

总结

理论上讲的通的道理只是理论上，小问题到了手上解决掉才能明白。简单的问题弄透也不容易，我记录一下这个思路省得忘了，能够有人用得上自然更好。当然谁要是能给我个更好的答案才是极好的。

java斐波那契优化,[LintCode]斐波纳契数列实现及优化

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 java斐波那契优化,[LintCode]斐波纳契数列实现及优化

相关斐波那契数列

相关斐波纳契数列

相关斐波那契数列

相关斐波那契数列

相关斐波那契数列

相关【LintCode 入门】366. 斐波纳契数列

相关斐波那契数列

相关斐波那契数列

相关斐波那契数列