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

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但是，什么是你能给我个提示吗谢谢！

最佳答案

如果A的大小将是N = n^2，那么如果在简单的情况下进行乘法运算，则algo的时间复杂度（我的意思是我们可以使用更聪明的Strassen算法）。现在，从主定理我们知道了。
因此，T(N) = 4T(N/4) + N^1.5可以是任何常量。

关于python - 递归算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55928297/