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

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

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

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

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

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

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

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

5 ответов

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

Однако это не так просто: сложная вещь заключается в добавлении d.getElement() к растущей строке: это сама по себе линейная операция, и она повторяется N раз. Следовательно, сложность вашей функции O(N^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). Этот пример не особенно интересен, но если вы посмотрите на что-то вроде времени выполнения mergesort или другого алгоритма разделения и покорения, вы можете получить лучшее представление о рекуррентных отношениях.


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


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

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

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

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


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

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

licensed under cc by-sa 3.0 with attribution.