行列有序n×m矩阵分治搜索算法的时间复杂度求解疑问

递归式的正确定义 #

设 T(r, c) 表示搜索 r 行 c 列的行列有序矩阵的时间复杂度，其中每次递归的基本操作（找中间索引、比较、条件判断）为 O(1)。

1. 基准情况 #

• 当 r=0 或 c=0（空矩阵），T(r,c) = O(1)；
• 当 r=1（单行），算法退化为类二分查找逻辑：每次仅递归搜索右半或左半子数组，因此 T(1,c) = O(logc)；
• 当 c=1（单列），同理 T(r,1) = O(logr)；
• 当 r=1 且 c=1，仅需一次比较，T(1,1)=O(1)。

2. 递归式构建 #

根据代码逻辑，分两种核心情况：

情况1：中间元素 mat[i][j] < key #

此时会递归调用两个子问题：

• 下半块矩阵：r/2 行，c 列，对应 T(r/2, c)；
• 右上象限矩阵：r/2 行，c/2 列，对应 T(r/2, c/2)；
  递归式为：

T(r,c) = T(r/2, c) + T(r/2, c/2) + O(1)

情况2：中间元素 mat[i][j] > key #

此时会递归调用两个子问题：

• 左半块矩阵：r 行，c/2 列，对应 T(r, c/2)；
• 右上象限矩阵：r/2 行，c/2 列，对应 T(r/2, c/2)；
  递归式为：

T(r,c) = T(r, c/2) + T(r/2, c/2) + O(1)

3. 时间复杂度推导 #

以最坏情况分析，取两种递归式中复杂度较高的场景：

方阵场景（n=m） #

递归树的内部节点总数为 O(n)，每个节点操作代价为 O(1)，总代价为 O(n)；叶子节点为单行/单列子问题，总数为 O(n)，每个叶子节点代价为 O(logn)，因此总时间复杂度为 O(n logn)。

一般n×m矩阵场景 #

• 若 n ≤ m：递归过程会分解出 O(n) 个单行子问题，每个代价 O(logm)，总复杂度为 O(n logm)；
• 若 m ≤ n：同理总复杂度为 O(m logn)；
  统一表述为 O(min(n,m) × log(max(n,m)))。

对原设想的纠正 #

你最初假设的 T(n)=3T(n/2)+O(1) 不符合该算法逻辑：该算法每次仅递归调用两个子问题（而非三个），且子问题规模并非均为 n/2 ×n/2，而是一个半规模子矩阵（如 n/2 ×m）加一个四分之一规模子矩阵（如 n/2 ×m/2），因此不能用单一参数的递归式描述。

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