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

Question

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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(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 или другого алгоритма разделения и покорения, вы можете получить лучшее представление о повторных отношениях.

Answer 5

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

Т (п) = Т (п - 1) + O (1)

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

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