Время выполнения рекурсивного алгоритма как повторение

Question

Я столкнулся с вопросом, спрашивающим, каково время выполнения следующего рекурсивного алгоритма.

  int F(int A[ ],int N) {

    if(N==1)

    return 1 ;
    return F(A,N-1)+1
}

Ответ - O (N), но я просто не знаю, как это оправдать.

Answer 1

Время выполнения можно получить по уравнению рекурсивного времени:

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

, а затем развернуть рекурсию:

T(n) = (T(n-2) + 1) + 1 = T(n-2) + 2 = (T(n-3) + 1) + 2 = T(n-3) + 3 =
... = T(1) + n - 1 = n = \Theta(n) = O(n)

Answer 2

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

Таким образом, каждый раз, когда функция вызывается, есть 1, если вызов, и 1обратный вызов.

Рекурсивный вызов имеет форму F(A,N-1), поэтому значение N уменьшается на 1 при каждом вызове, а ваш базовый случай равен N = 1, т. е. больше не будет рекурсивных вызовов, когда он достигнет 1.

Так что интуитивно очевидно, что существует N рекурсивных вызовов, и, поскольку каждый вызов выполняет операции в постоянное время (следовательно, незначительно), общее время выполнения составляет O (N)

Iнадежда, что объясняет.