algorithm - 如果基本情况是 O(n)，那么递归是多少？

Question

我们必须创建一个算法并找到并解决它的递归。发现复发让我难住了..

foo(A, C)
  if (C.Length = 0)
    Sum(A)
  else
    t = C.Pop()
    A.Push(t)
    foo(A,C)
    foo(A,C)

最初 A 为空且 C.Length = n。我不能给出真正的算法，因为那是不允许的。

我的导师告诉我，我可能会尝试使用 2 个变量。这就是我想出的：

T(n, i) = { n                if i =  0
            2*T(n, i-1) + C  if i != 0

我无法解决它，所以我也尝试只用一个变量来解决重复问题：

T(n) = { n0                  if n =  0
         2*T(n-1) + C        if n != 0

其中 n0 是 n 的初始值。

您如何从基本情况复杂度为 O(n) 的算法中形成递归？

score 2 · Accepted Answer

如果 C 的大小为 n，则设 f(n) 为复杂度。令 N 为 C 的原始大小。

那么 f(0) = N 和 f(n) = 2 * f(n - 1) + c。

这有解 f(n) = N * 2^n + (2^n - 1) * c，所以 f(N) = O(N * 2^N)。

1 回答 1