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

问题描述：

如果我们有这样的代码（伪）这个递归调用的时间复杂度是多少？假设以下没有说明的东西被认为是恒定时间。递归算法的时间复杂度（伪代码）

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），但我不太明白指数复杂度是如何产生的，所以我想知道它是否可以代替？

你在哪里分析自己的复杂性问题？您需要计算每个函数被调用的频率。这产生一个依赖于使用变量的数字，比如'a + 2b + c^a'或类似的东西。之后，派生一个复杂类很容易。 – Zabuza

@ikegami应该写成b - 1. – tiggybits

假设b在递归函数中是局部的，所以b-1不会影响主循环中的b – tiggybits

答

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

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

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

f()被称为N*N = N² = O(N²)倍。

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

正如你所看到的，内循环的起始位置并不重要，复杂性将是相同的。

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

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

我们已经知道这两个外环路O(N²)，和我们正在做的N倍，所以我们得到O(N³)。我们可以看到指数是嵌套量。

如果我们开始展开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)时间。

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

相关推荐