如何合并递归算法的外层复杂度与单次函数调用的复杂度

统一复杂度表达式推导 #

首先对齐变量定义：

• 设n为输入二维矩阵的行数，矩阵列数为固定常量（若列数与n正相关可后续调整系数）
• k为最坏情况下的最大递归深度
• 符合你给出的最坏前提：每次矩阵切片几乎不删除元素，递归输入的矩阵行数始终近似为n，且循环中所有i都不满足跳过条件，每次都会触发递归调用

步骤1：确认单次函数调用的开销

你提到的单次函数调用复杂度O(n)是合理的，补充矩阵切片的开销验证：MATLAB逻辑索引切片需要遍历所有行完成条件判断、拷贝符合条件的行，最坏情况切片后行数仍为n，若列数为固定常量，切片开销可合并进O(n)的单次调用开销中，无需额外增加阶数。

步骤2：修正递归总调用次数

你之前写的O(k^n)是变量顺序写反了，最坏情况下每一层递归的单次调用都会触发n次下一层递归，递归深度为k时，总调用次数为等比数列求和：1 + n + n² + ... + n^k，总阶数为O(n^k)。

步骤3：合并得到统一复杂度

总时间复杂度为单次调用开销 × 总调用次数，因此最坏情况下的统一大O表达式为：

O(n * n^k) = O(n^(k+1))

特殊场景调整

• 如果矩阵为n×n的方阵，列数与行数正相关，单次切片开销升级为O(n²)，对应总复杂度调整为O(n^(k+2))
• 如果最坏情况下每次切片仅删除1行，递归深度k≈n，此时总复杂度可简化为O(n^n)，属于指数级复杂度。

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