它要求获得斐波那契数 sequence.Can 搞不懂为什么我的代码总是超时

Question

这是 Hackerrank.The 中的一个问题 link 在这里：fibonacci-finding-easy

给出递归序列F(n+2)=F(n+1)+F(n)的两个初值F(0),F(1)分别赋给A,B和要求它的第 N 项，输出它模 (10^9 + 7)。我知道经典的解决方法是使用快速矩阵 multiplication.And 我在 Python3.The 测试中写它 IDE 没有 problems.But 我不知道为什么我的代码总是得到 timeout.Here 是我的代码：

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 进行了整个递归过程所以 slow.But 我在我的 IDE 中测试了很多次并且一切正常，存在没有 TLEs.Is 有什么我错过的吗？

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

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

它要求获得斐波那契数 sequence.Can 搞不懂为什么我的代码总是超时

It asks to get a term of Fibonacci sequence.Can't make out why my code always gets timeout

algorithm

fibonacci

python-3.x