Что такое рецидив, если базовый вариант 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

Пусть f (n) будет сложностью, если C имеет размер 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).