Сложности во время выполнения для рекурсивных алгоритмов

Question

Я искал высоко и низко и не могу найти много материала, связанного со сложностями во время выполнения, рекурсией и Java.

В настоящее время я изучаю сложности времени выполнения и нотацию Big-O в своем классе Algorithms, и у меня возникают проблемы с анализом рекурсивных алгоритмов.

private String toStringRec(DNode d)
{
   if (d == trailer)
      return "";
   else
      return d.getElement() + toStringRec(d.getNext());
}

Это рекурсивный метод, который просто выполняет итерацию по двусвязному списку и распечатывает элементы.

Единственное, что я могу придумать, это то, что он имеет сложность во время выполнения O (n), так как количество рекурсивных вызовов методов будет зависеть от количества узлов в DList, но я все еще не чувствую себя комфортно с этим ответом.

Я не уверен, должен ли я учитывать добавление d и d.getNext().

Или я просто не в курсе, а сложность во время выполнения постоянна, так как все, что он делает, это извлекает элементы из DNodes в DList?

Answer 1

На первый взгляд, это похоже на классический случай хвостовой рекурсии по модулю cons , обобщение хвостового вызова.Это эквивалентно циклу с количеством итераций.

Однако, это не так просто: сложность здесь заключается в добавлении d.getElement() к растущей строке: это само по себе линейная операция, и она повторяется N раз.Следовательно, сложность вашей функции составляет O(N^2).

Answer 2

Это довольно простой пример, но хитрость состоит в том, чтобы определить рекуррентное отношение, которое является функцией времени выполнения данного входного размера в терминах меньших входных размеров.Для этого примера, если предположить, что работа, выполняемая на каждом шаге, занимает постоянное время C, и предположить, что базовый вариант не работает, это будет:

T(0) = 0
T(n) = C + T(n-1)

Затем можно найти время выполнения, используя подстановку, чтобы найтисерия:

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC

По определению O это уравнение равно O (n).Этот пример не особенно интересен, но если вы посмотрите на что-то вроде времени выполнения сортировки слиянием или другого алгоритма «разделяй и властвуй», вы можете получить лучшее представление о рекуррентных отношениях.

Answer 3

Если T (n) - количество элементарных операций (в данном случае - когда мы вводим тело функции, любая из строк внутри выполняется не более одного раза, и все, кроме второго возврата, не O (1) ) выполняется путем вызова toStringRec для списка из n элементов, затем

  T(0) = 1  - as the only things that happen is the branch instruction and a
              return
  T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the
              function besides calling toStringRec is some constant time stuff and
              concatenating strings that takes O(n) time; and we also run
              toStringRec(d.getNet()) which takes T(n-1) time

На данный момент мы описали сложность алгоритма. Теперь мы можем вычислить замкнутую форму для T, T (n) = O (n ** 2).

Answer 4

Для таких рекурсивных алгоритмов обычно можно написать рекурсивное уравнение для вычисления порядка. Обычно указывается количество инструкций, выполненных с помощью T (n). В этом примере мы имеем:

T (n) = T (n - 1) + O (1)

(Предположим, что функция getElement выполняется за постоянное время.) Решение этого уравнения тривиально T (n) = O (n).

Это был общий случай. Однако иногда вы можете проанализировать алгоритм без написания такого уравнения. В этом примере вы можете легко утверждать, что к каждому элементу обращаются максимум один раз, и каждый раз выполняется некоторая постоянная работа; таким образом, для выполнения этой работы требуется O (n).

Answer 5

Алгоритм имеет сложность времени выполнения O (n), как вы предлагаете. В вашем списке есть n элементов, и алгоритм будет выполнять почти фиксированный объем работы для каждого элемента (эта функция - доступ к элементам и следующим элементам плюс новый вызов toStringRec). Извлечение элемента из DNode занимает постоянное время, а постоянное время отбрасывается в нотации big-O.

Интересная вещь о рекурсивных методах (в большинстве случаев) состоит в том, что они также O (n) в сложности пространства тоже. Новая запись стека (для хранения параметров, переданных методу) создается для каждого вызова toStringRec, который вызывается n раз.