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

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

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

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

Answer 2

Если 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 3

Это довольно простой пример, но хитрость заключается в том, чтобы определить рекуррентное отношение, которое является функцией времени выполнения заданного входного размера в терминах меньших входных размеров. Для этого примера, если предположить, что работа, выполняемая на каждом этапе, занимает постоянное время 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 4

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

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

Answer 5

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

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

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

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