递归算法M3的最坏情况时间复杂度（WCTC）求解

首先给出函数实现代码：

void M3(int N, int M){
 if(N > 0)
     M3(M, N - 1) ;
 else if(M > 0)
     M3(M - 1, N) ;
}

复杂度推导过程 #

我们通过统计递归调用的总次数来分析时间复杂度（每次调用仅执行条件判断，无额外复杂操作，调用次数直接对应时间开销）。定义T(N,M)为调用M3(N,M)时的总调用次数（包含自身）：

• 当N>0时：T(N,M) = 1 + T(M, N-1)（1是当前调用，加上后续递归的调用次数）
• 当N=0且M>0时：T(0,M) = 1 + T(M-1, 0)
• 当N=0且M=0时：T(0,0)=1（仅当前调用，无后续递归）

实例验证 #

举几个具体例子验证：

• 例1：N=3，M=2，计算得总调用次数为6，而N+M=5，调用次数为N+M+1
• 例2：N=0，M=5，总调用次数为6，即M+1（等价于N+M+1）
• 例3：N=4，M=3，总调用次数为8，即N+M+1

结论 #

无论初始参数如何，总调用次数始终是N+M+1量级，因此该函数的最坏情况时间复杂度是O(N+M)，你朋友的结论是正确的。

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