算法時間複雜度改進

• 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;這樣就可以極大加快速度。