c++ - 优化代码:斐波那契算法

我正在研究真正大数(第100k个数)的斐波那契算法。我需要使运行速度更快，但是仅需几秒钟，我就没了主意。有什么办法可以使其更快？感谢帮助。

#include <iostream>

using namespace std;
int main() {


    string elem_major = "1";
    string elem_minor = "0";
    short elem_maj_int;
    short elem_min_int;
    short sum;
    int length = 1;
    int ten = 0;

    int n;
    cin >> n;


    for (int i = 1; i < n; i++)
    {

        for (int j = 0; j < length; j++)
        {
            elem_maj_int = short(elem_major[j] - 48);
            elem_min_int = short(elem_minor[j] - 48);
            sum = elem_maj_int + elem_min_int + ten;
            ten = 0;
            if (sum > 9)
            {
                sum -= 10;
                ten = 1;
                if (elem_major[j + 1] == NULL)
                {
                    elem_major += "0";
                    elem_minor += "0";
                    length++;
                }
            }
            elem_major[j] = char(sum + 48);
            elem_minor[j] = char(elem_maj_int + 48);
        }
    }

    for (int i = length-1; i >= 0; i--)
    {
        cout << elem_major[i];
    }

    return 0;
}

最佳答案

无论您对给定代码执行的优化有多好，在不更改基础算法的情况下，您都只能对其进行少量优化。您的方法具有线性复杂度，对于较大的值，它将很快变得缓慢。斐波纳契数的更快实现是对矩阵执行exponentiation by squaring矩阵:

0 1
1 1

这种方法将具有对数复杂度，即渐近更好。对这个矩阵进行一些幂运算，您会注意到n + 1 st Fibonacci数字在其右下角。