求二维矩阵最大全1正方形递归代码的时间复杂度

你的递归代码在最坏情况下（比如整个矩阵全为1）的时间复杂度是指数级的，具体分析如下：

递归关系式建立 #

定义T(i,j)为计算solveRec(mat, i, j)所需的时间：

• 当i >= m或j >= n（越界）时，T(i,j) = O(1)，仅需直接返回0。
• 对于矩阵内的位置(i,j)，代码会先执行三个递归调用：right（(i,j+1)）、diagnol（(i+1,j+1)）、down（(i+1,j)），之后才判断当前元素值。因此无论mat[i][j]是0还是1，都需要消耗这三个子调用的时间，加上当前步骤的常数时间，递归式为：

  T(i,j) = T(i,j+1) + T(i+1,j+1) + T(i+1,j) + O(1)
  

复杂度推导 #

每个递归调用会分解为三个独立的子问题，且不同的父调用会重复计算同一个(i,j)位置（比如(1,1)会被(0,0)的diagnol调用、(0,1)的down调用、(1,0)的right调用），导致总调用次数呈指数级增长。

• 当矩阵为m×n时，最坏情况下（全1矩阵）的时间复杂度上界为O(3^(m+n))，这是因为递归树的每个节点最多有3个子节点，递归深度最多为m+n（从(0,0)到边界最多需要m+n步）。
• 更紧凑的上界为O(3^min(m,n))，当m和n差距较大时，比如m=1、n=k，此时复杂度退化为O(n)（线性），因为down和diagnol调用会直接触发边界条件，仅right会持续递归。

优化方向 #

这种纯递归解法的效率极低，因为大量重复计算。可以通过记忆化搜索（将已计算的(i,j)结果存储在二维数组中）将时间复杂度优化到O(mn)，或者进一步用动态规划的迭代版本实现，空间复杂度还能优化到O(n)。

内容的提问来源于stack exchange，提问作者dhirunand