for循环中递归的时间复杂度 [英] Time complexity for recursion in for loop

问题描述

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

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

Please help me understand time complexity of above pseudo code.

推荐答案

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

Your recursive code has the following properties:

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

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

Mathematically, we can model the total work done as a recurrence relation, letting T(n) denote the amount of work done when you call func(n):

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

让我们试试这个，看看我们发现了什么.

Let's play around with this and see what we find.

• 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.

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

It might not be obvious just by looking at this, the numbers here are actually given by the formula

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

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

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

We can check this briefly as follows:

• T(0) = (6¹ - 1)/5 = 5/5 = 1.
• T(1) = (6² - 1)/5 = 35/5 = 7.
• T(2) = (6³ - 1)/5 = 215/5 = 43.

• T(0) = (6¹ - 1) / 5 = 5 / 5 = 1.
• T(1) = (6² - 1) / 5 = 35 / 5 = 7.
• T(2) = (6³ - 1) / 5 = 215 / 5 = 43.

渐近地，这意味着 T(n) = Θ(6ⁿ)，所以整体运行时间是 Θ(6ⁿ).

Asymptotically, this means that T(n) = Θ(6ⁿ), so the overall runtime is Θ(6ⁿ).

那么... (6ⁿ⁺¹ - 1)/5 是从哪里来的?请注意

So... where did (6ⁿ⁺¹ - 1) / 5 come from? Notice that

• T(0) = 1
• T(1) = 6 ·1 + 1
• T(2) = 6² ·1 + 6 ·1 + 1
• T(3) = 6³ ·1 + 6² ·1 + 6 ·1 + 1

• T(0) = 1
• T(1) = 6 · 1 + 1
• T(2) = 6² · 1 + 6 · 1 + 1
• T(3) = 6³ · 1 + 6² · 1 + 6 · 1 + 1

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

More generally, T(n) seems to have the form

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

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

这是几何级数的和，简化为 (6ⁿ⁺¹ - 1)/5.

This is the sum of a geometric series, which simplifies to (6ⁿ⁺¹ - 1) / 5.

这篇关于for循环中递归的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！