时间戳

首页 > 解决方案 > 递归算法的时间复杂度

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？你能给我一个提示吗？谢谢！

标签： pythonalgorithmrecursiontime-complexitybig-o

解决方案

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

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

推荐阅读