递归树的时间复杂度

Question

递归调用 Fn(1),Fn(2),Fn(3),...,Fn(n-1) 来求解 Fn(n) 的函数 Fn(n) 的时间复杂度是多少。Fn(1) =1 作为基本条件给出。它会是 O(n^n) 或更少。我认为它应该小于 O(n^n) 但我无法找到一种方法来获得这种递归的正确复杂性。

Fn(4) 的递归树将是这样的

              Fn(4)
         /        |     \
      Fn(3)    Fn(2)   Fn(1)
     /   \        /
   Fn(2) Fn(1) Fn(1)
   /
Fn(1)

Answer 1

重现看起来像这样：

T(1) = 1
T(n) = ? T(i), from i = 1 to n-1

乍一看不是特别有用，是吧？所以让我们把它分解成子问题，看看它们是什么样的：

   T(5) = T(4) + T(3) + T(2) + T(1)
=> T(5) = T(4) + T(3) + T(2) + 1

   // The sub problems
   T(4) = T(3) + T(2) + 1
   T(3) = T(2) + 1
   T(2) = 1

现在让我们将这些子问题中的一些替换回我们原来的问题：

   T(5) = T(4) + T(3) + T(2) + 1
=> T(5) = T(4) + T(4)
=> T(5) = 2T(4)

所以我们可以推导出循环实际上是这样的：

T(n) = 2T(n-1)
T(n-1) = 2T(n-2)

所以我们可以将我们的递归重写为

T(n) = 2[ 2T(n-2) ]
T(n) = 2[ 2 [ 2T(n-3) ] ]
...
T(n) = 2^k [ T(n-k) ]

由于我们之前描述的基本情况是

T(1) = 1
// Therefore
n = 1
k = 1
n = k

现在我们可以在我们的循环中替换为：

   T(n) = 2^n [ T(1) ]
   T(n) = 2^n [ O(1) ]
=> T(n) = 2^n

因此，您的复发是 O(2^n)