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) 的算法中形成递归？

Answer 1

如果 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)。