请求分析嵌套递归函数foo1的Big-O时间复杂度

嘿，咱们来一步步拆解这个递归函数的时间复杂度，你之前猜测的O(n^n)其实不太准确，咱们仔细理清楚：

首先，我们定义T(a,b,c)为调用foo1(a,b,c)时的时间复杂度，接下来分情况推导递归关系：

1. 当c=1时的基线情况 #

此时if (c>1)的条件不成立，没有递归调用，函数只会执行两层嵌套循环：外层循环a次，内层循环b次，总共执行a*b次基础操作。所以：

T(a,b,1) = O(a*b)

2. 当c>1时的递归情况 #

此时每一次内层循环（共a*b次循环）都会触发一次foo1(a,b,c-1)的递归调用，因此递归关系式为：

T(a,b,c) = a*b * T(a,b,c-1)

我们可以展开这个递归式来求解：

• 第1次展开：T(a,b,c) = (a*b) * T(a,b,c-1)
• 第2次展开：T(a,b,c) = (a*b)^2 * T(a,b,c-2)
• ...
• 第c-1次展开：T(a,b,c) = (a*b)^(c-1) * T(a,b,1)

把基线情况的T(a,b,1)=O(a*b)代入进去，得到：

T(a,b,c) = (a*b)^(c-1) * O(a*b) = O( (a*b)^c )

3. 不同场景下的复杂度解读 #

• 如果c是一个固定常数，那么复杂度是多项式级的，比如c=3时，复杂度为O(a³*b³)；
• 如果c是和a、b一起增长的变量（比如假设a=b=c=n），那么复杂度会变成O( (n*n)^n ) = O(n^(2n))，这是一个增长极快的指数级复杂度，和你之前想的O(n^n)有区别，因为这里是(a*b)的c次方，而非单一变量的n次方。

内容的提问来源于stack exchange，提问作者Nailkaiser-Sama