Анализ рекурсии в алгоритмах

Question

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

function h(N) { 
    if (N==1) return 3; 
    else { 
     sum = 1; 
     i = 0; 
     while (i < h(N-1)) 
      sum = sum + i; 
      i = i + 1; 
     return sum; 
    } 
} 

По мне, так как ч (N-1) называется многократно в цикле в то время, в то время как контур должен работать столько, сколько раз, как то, что возвращается ч (N-1). Кроме того, вызов функции h (N-1) в цикле while также произойдет много раз. Таким образом, в соответствии со мной, я должен получить что-то вроде этого:

Т (N) = Т (N-1) * H (N-1) + C * H (N-1) + D

где
1. T (N) - это время работы,
2. T (N-1) * H (N-1), поскольку один рекурсивный вызов h (N-1) будет принимать T (N-1), и поскольку он пересчитывается каждый раз при сравнении, он будет называться Н (N-1) раз. (где H (N-1) - это значение, возвращаемое вызовом)
3. и C * H (N-1) - это время выполнения операторов внутри цикла while (так как цикл while запускает H (N- 1) раз.

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

Спасибо!

Answer 1

Попробуйте понять это в два этапа, сначала рассмотрите эту более простую функцию, где мы заменяем петлю while на if.

function g(N) { 
    if (N==1) return 3; 
    else { 
     sum = 1; 
     i = 0; 
     if(i < g(N-1)) 
      sum = sum + i; 
      i = i + 1; 
     return sum; 
    } 
} 

Здесь мы получаем повторение:

G(N) = G(N-1) + O(1) 

До сих пор, так хорошо? Здесь работа по вычислению g (N) включает решение меньшей задачи g (N-1) плюс постоянный объем работы.

Теперь вернемся к исходной функции h (N). Что изменилось? Теперь работа по вычислению h (N) включает в себя решение подзадачи h (N - 1), h (N-1) раз. И в каждый из этих времен (то есть в цикле while) мы выполняем постоянный объем работы. Существует также еще один постоянный объем работы, который выполняется только один раз в h (N), то есть вне цикла while. Таким образом, мы в основном получаем:

H(N) = H(N - 1) *{H(N - 1) + O(1)} + O(1) 

Мы можем переписать выше, сделав замену T(n) = H(n) + O(1). Таким образом, мы получаем:

T(N) = H(N - 1) * T(N - 1) + O(1) 

Answer 2

Предположим, что при выполнении Н (N), значение h (N-1) пересчитывается на каждой итерации цикла (что, вероятно, имеет место для большинства языков и большинства компиляторов)