time-complexity - for循环中递归的时间复杂度

Question

func(n){
 if(n == 0){
   //print sth
   return;
 } 
 for(i=1;i<=6;i++){
   func(n-1)
 }
}   

请帮助我理解上述伪代码的时间复杂度。

Answer 1

您的递归代码具有以下属性:

当您使用参数 0 调用该函数时，它会执行恒定的工作量然后返回。

当您使用参数 n > 0 调用该函数时，它会执行恒定的工作量并对大小为 n - 1 的问题进行六次递归调用。

在数学上，我们可以将完成的总工作量建模为递推关系，让 T(n) 表示当您调用 func(n) 时完成的工作量。 :

T(0) = 1

T(n) = 6T(n - 1) + 1

让我们玩这个，看看我们发现了什么。

T(0) = 1。

T(1) = 6T(0) + 1 = 6 + 1 = 7。

T(2) = 6T(1) + 1 = 6(7) + 1 = 43。

T(3) = 6T(2) + 1 = 6(43) + 1 = 259。

T(4) = 6T(3) + 1 = 6(259) + 1 = 1555。

看这个可能不明显，这里的数字实际上是由公式给出的

T(n) = (6ⁿ⁺¹ - 1) / 5

我们可以简单地检查如下:

T(0) = (61 - 1)/5 = 5/5 = 1。

T(1) = (62 - 1)/5 = 35/5 = 7。

T(2) = (63 - 1)/5 = 215/5 = 43。

渐近地，这意味着 T(n) = Θ(6n)，因此总运行时间为 Θ(6n)。

那么...... (6n+1 - 1)/5 从哪里来？请注意

T(0) = 1

T(1) = 6 · 1 + 1

T(2) = 62 · 1 + 6 · 1 + 1

T(3) = 63 · 1 + 62 · 1 + 6 · 1 + 1

更一般地，T(n) 似乎具有以下形式

6ⁿ + 6^n-1 + ... + 6¹ + 6⁰.

这是几何级数的总和，可简化为 (6n+1 - 1)/5。