c++ - 这个矩阵博览会代码是对数的吗？

Question

我想用对数时间计算第 n 个斐波那契数。所以，我写了这个函数

vector<vector<ll> > expon(ll k)
{
    if(k==1)
    {
        vector<vector<ll>> A({{1,1},{1,0}});
        return A;
    }
    auto A = expon(k/2);
    ll tmp[2][2] = {{0,0},{0,0}};
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                tmp[i][j] += (A[i][k]*A[k][j])%modv;

    vector<vector<ll>> B({{tmp[0][0],tmp[0][1]},{tmp[1][0],tmp[1][1]}});
    if(k%2)
        return vector<vector<ll>>({{(tmp[0][0]+tmp[0][1])%modv,tmp[0][0]},{(tmp[1][0]+tmp[1][1])%modv,tmp[1][0]}});
    else
        return B;
}

但有些我认为它花费了太多时间。所以我想知道，它实际上是对数的吗？我是说我的代码。

Answer 1

复杂度是对数的，但实现不是最优的。您不需要递归，也不需要为矩阵的每个幂创建单独的 vector 实例。另一个评论 - 你有重复的变量 k 这会导致警告，具体取决于编译器设置。

有一种方法可以检查给定的代码片段是否是对数的 - 测量输入 n、n^2、n 所花费的时间^4。如果复杂度是对数的，则每个测试的时间应该是前一个测试的大约两倍(还要记住，在短时间内测量可能不准确)。