具有嵌套递归的方法的大 O 复杂性

Question

只是想弄清楚以下算法的 Big-O 复杂度：

function foo1(a,b,c)
Begin
  for i:=1 to a do begin
    for j:=1 to b do begin
      if (c>1) then
        x=y+foo1(a,b,c-1);  
    end;
  end;  
End;

所以，我基本上是怎么想的：这个函数有 O(n^n) 复杂度，如果 a、b 和 c 是变量。不过我不太确定。

Answer 1

让我们把问题分成几个部分：

1) 第一个循环：从1到a，这意味着它需要a 完成循环的步骤。

2) 第二个循环：从1到b，这意味着它需要b x a 来完成这些循环。为什么？因为在 a 的每个循环中，您都执行 b 循环。这意味着：b0 + b1 + b2 ... ba。因此 -> a*b

3) 然后你应用一个递归步骤。该递归在第二个循环中重复 c 次。这意味着对于 b 中的每次迭代，您将重复整个过程。意思是 (a * b)0 * (a * b)1 * (a * b)2 ... (a * b)c 。因此 -> O((a*b)^c)

具有嵌套递归的方法的大 O 复杂性

Big O complexity of a method with a nested recursion

algorithm

recursion

complexity-theory

loops