递归算法的时间复杂度（伪代码）

Question

如果我们有这样的代码（伪），这个递归调用的时间复杂度是多少？假设下面没有说明的任何东西都被认为是常数时间。

a,b,c > 0

//some code above, then we get here 

for i = 0 to a
    recursive(i,b)

//code continues

FUNCTION recursive(i,b)
if b = 0
    return 0

for j = i+c to a
    recursive(j,b-1)
ENDFUNC

编辑我主要无法确定它是否是指数的。深度显然是 b 并在递归函数中执行一个调用，给出 O(b*a)，但主循环也调用它一次，这让我认为它应该是总的：O(a^2 * b)，但我不太明白指数复杂度是如何产生的，所以我想知道它是否可以代替它？

Answer 1

首先，我们先来看两个简单的嵌套循环：

for i (1..N) {
   for j (1..N) {
      f();
   }
}

for i (1..N) {
   for j (i..N) {
      g();
   }
}

f() 被称为 N*N = N2 = O(N2) 次。

g() 称为 N+(N-1)+...+5+4+3+2+1 = N(N+1)/2 = N2/2 + N/2 = O(N2) 次。

如您所见，内循环从哪里开始并不重要；复杂度将是相同的。

其次，让我们看看如果添加一层嵌套会发生什么。

for i (1..N) {
   for j (1..N) {
      for k (1..N) {
          h();
      }
   }
}

我们已经知道两个外部循环是 O(N2)，我们正在这样做 N 次，所以我们得到 O(N3)。可以看出指数就是嵌套的数量

如果我们开始展开 recursive，我们得到

for i2 = i+c to a
    recursive(i2, b-1)

也就是

for i2 = i+c to a
   for i3 = i2+c to a
       recursive(i3, b-2)

也就是

for i2 = i+c to a
   for i3 = i2+c to a
       for i4 = i3+c to a
           recursive(i4, b-3)

等等

如您所见，您有 b 个嵌套循环，迭代 a-c 个元素的子集。应用我们上面学到的知识，recursive 需要 O((a-c)b) 时间。

整个代码（即对 recursive 的调用加上外循环）增加了另一层，因此需要 O((a-c)b * a)次.

递归算法的时间复杂度（伪代码）

Time complexity of recursive algorithm (pseudo code)

algorithm

time-complexity

analysis