algorithm - 它要求获得斐波那契数列的一项。无法弄清楚为什么我的代码总是超时

Question

这是 Hackerrank 中的一个问题。链接在这里:fibonacci-finding-easy

给出递归序列F(n+2)=F(n+1)+F(n)的两个初值F(0),F(1)分别赋给A,B求它的第 N 项，输出模数 (10^9 + 7)。我知道经典的解决方法是使用快速矩阵乘法。我用 Python3 编写它。我的 IDE 中的测试没有问题。但我不知道不知道为什么我的代码总是超时。这是我的代码:

def mul22(a, b):
    r = [[0, 0], [0, 0]]
    r[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 1000000007
    r[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % 1000000007
    r[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % 1000000007
    r[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % 1000000007
    return r

def MatrixPow(A, n):
    if n == 1:
        return A
    if n % 2 == 1:
        return mul22(mul22(MatrixPow(A, n // 2),MatrixPow(A, n // 2)), A)
    return mul22(MatrixPow(A, n // 2), MatrixPow(A, n // 2))

for i in range(int(input())):
    A,B,N= map(int,input().split())
    if N == 1:
        print(B % 1000000007)
    else:
        print(mul22(MatrixPow([[1, 1],[1, 0]], N - 1),[[B,1],[A,1]])[0][0] % 1000000007)

首先我认为问题是 10 ** 9 + 7 使整个递归过程如此缓慢。但是我在我的 IDE 中测试了很多次，一切正常，不存在 TLE。有什么我遗漏的吗？

Answer 1

您编写 MatrixPow 函数的方式实际上并未在 O(log(n)) 中运行。它的运行时间是O(N)。

考虑这个幂函数:

def power_n(a,b):
    print 1
    if b==0:
        return 1
    if b%2==1:
        return (((power_n(a,b/2)*power_n(a,b/2))%MOD)*a)%MOD
    return (power_n(a,b/2)*power_n(a,b/2))%MOD

还有这个:

def power_log(a,b):
    print 2
    if b==0:
        return 1
    k = power_log(a,b/2)
    if b%2==1:
        return (((k*k)%MOD)*a)%MOD
    return (k*k)%MOD

第一种和第二种的区别在于，在第二种情况下我们只遍历整个递归树一次(因为一旦我们有了某个值，我们就保存它)，而在第一种情况下，我们一次又一次地计算它。

虽然看起来一样，但第一个函数类似于传统循环，运行时间为 O(n)，而第二个函数实际上是幂函数，运行时间为 O(log n)

PS:n 表示b，即。权力

编辑:

分析: (我只是在两个函数中都添加了打印语句并运行了它，这是结果)

power_n(6,20)
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    Out[22]: 414469870

power_log(6,20)
    2
    2
    2
    2
    2
    2
    Out[25]: 414469870

查看函数调用次数的差异。