一点一点前进...

0%

斐波那契数列算法及时间复杂度分析

发表于 分类于 ， Disqus：

斐波那契数列是一个很有意思的数列，应用领域非常广。
定义：
F(n+1)=F(n)+F(n-1)
有意思的是，F(n)/F(n+1)趋于黄金分割0.618。

如何计算斐波那契数呢？
最朴素的思想，利用定义。
算法1代码如下： 

1
2
3
4
5
6
7
8
9
static int Fibonacci1(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }

    return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}

分析下算法复杂度：
T(n+1)=T(n)+T(n-1)=2*T(n-1)+T(n-2)=…=F(n)+F(n-1)=F(n+1)
由于直接递归调用，结果中的每一个1都来自最底层的F(1)和F(2)
那么为了求第n个数，就要调用F(n)次函数。
由于斐波那契数列是指数增长，所以该算法的时间复杂度也是指数增长，即O(2^n)

仔细想下，从头开始往后算，也不过是线性复杂度，比算法1好太多了
于是得到算法2： 

1
2
3
4
5
6
7
8
9
10
11
12
static int Fibonacci2(int n)
{
    int[] a = new int[n];
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i < n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }

    return a[n - 1];
}

时间复杂度就是O(n)

求斐波那契数列的算法还能再快一些吗？
答案是肯定的
算法3：
借助下面公式所示的结论：
$$
\left(\begin{matrix}
F_{n+1}\
F_n\
\end{matrix}\right)
=
\left(\begin{matrix}
1 & 1\
1 & 0\
\end{matrix}\right)
\left(\begin{matrix}
F_{n}\
F_{n-1}\
\end{matrix}\right)
\Rightarrow
\left(\begin{matrix}
F_{n+1} & F_{n}\
F_n & F_{n-1}\
\end{matrix}\right)
=
{\left(\begin{matrix}
1 & 1\
1 & 0\
\end{matrix}\right)}^n
$$
我们求一个矩阵的n次方即可
两个2维矩阵的乘法次数可以看作常量
矩阵额n次方利用分治法，只需要O(lg n)的复杂度就能计算出来
所以该算法的复杂度是O(lg n)，比算法2又快了很多，特别是数字非常大的时候
比如n从1亿变成4亿，算法2需要的时间要变成原来的四倍，但是算法3仅仅增加了个常数2(lg 4=2)
算法代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static int Fibonacci3(int n)
{
    int[,] a = new int[2, 2] { { 1, 1 }, { 1, 0 } };
    int[,] b = MatirxClub(a, n);
    return b[1, 0];
}

static int[,] MatirxClub(int[,] a, int n)
{
    if (n == 1) { return a; }
    else if (n == 2) { return Matirx(a, a); }
    else if (n % 2 == 0)
    {
        int[,] temp = MatirxClub(a, n / 2);
        return Matirx(temp, temp);
    }
    else
    {
        int[,] temp = MatirxClub(a, n / 2);
        return Matirx(Matirx(temp, temp), a);
    }
}

static int[,] Matirx(int[,] a, int[,] b)
{
    int[,] c = new int[2, 2];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                c[i, j] += a[i, k] * b[k, j];
            }
        }
    }
    return c;
}

随手写了个测试程序对比它们的效率。
算法1计算n=42和算法2计算n=400 000 000所需的时间差不多。
由此可见，指数时间复杂度的算法太可怕…
但是算法3对于n=400 000 000也几乎一瞬间就算完了。