python - 递归算法的时间复杂度

Question

A 是一个 n×n 矩阵。考虑一个函数 algo(A) 返回:

def algo(A):
    return algo(A[:n//2, :n//2]) + algo(A[:n//2, n//2:]) + algo(A[n//2:, :n//2]) + \
           algo(A[n//2:, n//2:]) + A.transpose() * A

时间复杂度的公式为O(log(a*n) + n^b)。该问题要求解决 a 和 b。我收集到，由于矩阵乘法，b=3。但是，什么是？你能给我一个提示吗？谢谢!

Answer 1

如果 A 的大小为 N = n^2，则 algo 的时间复杂度为 T( N) = 4T(N/4) + N^1.5 如果乘法是在一个简单的情况下完成的(我的意思是我们可以使用更聪明的东西，比如 Strassen 算法)。现在，根据主定理，我们知道 T(N) =\Theta(N^1.5) =\Theta(n^3)。

因此，a可以是任意常数值。