算法时间复杂度改进

• 2022 年 3 月 13 日
• 筆記
• 蓝桥杯

1.求斐波那契数列

斐波那契数列可以使用递归的方式进行求解，但是递归对于栈空间占用太大了

int fenbo(int n)
{
    if(n == 1)
        return 1;
    if(n == 2)
        return 1;
    return fenbo(n - 1) + fenbo(n  - 2);
}

以上的算法是一个中规中矩的球斐波那契数列的例子，运行一些小的数字时还可以出来。

第40项

40 102334155 625ms.

查看第100项是会不显示，时间太长。
但是一但为极大的项，则要等好久，会超过时间限制；
所以可以使用记忆化搜索，降低时间复杂度。
即使用数组将查找过的斐波那契数进行储存，在要使用到时候可以使用，而不用再次进行调用；

long long num[10000];
//改进斐波那契数列
long long gaifei(int n)
{
    if(num[n])
        return num[n];
    if(n == 1 || n == 2)
    {
        num[1] = 1;
        num[2] = 1;
        return 1;
    }

    num[n] = num[n - 1] + num[n - 2];

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

在拥有上面改进后的算法，可以发现速度十分快。
第40项

40 102334155 0ms.

第100项

100 12586269025 16ms.

可以看出改进后的算法速度很快。

2.求a的n次方幂（递归）

求a的n次方，使用for循环即可。但是时间复杂度是O(2^n),对于一个算法来说，这个时间复杂度显然是不能合格的，所以要改进此算法。

int cifang(int a, int n)
{
    if(n == 0)
        return 1;
    int res = a;
    int ex = 1;
    while ((ex << 1) < n)   //判断是否超过n次
    {
        res  *= res;        //每次与自己相乘
        ex<<=1;             //左移一位，平方
    }
    return res * cifang(a, n - ex); //将相差的n - ex次方放入递归求解。
}

将O(2^n)降为O(logn),每次乘与之相同的数字，就是22,44,16*16;这样就可以极大加快速度。