algorithm - 递归树的时间复杂度

Question

函数 Fn(n) 递归调用 Fn(1),Fn(2),Fn(3),...,Fn(n-1) 求解 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)