Рубрики

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 9

Временная сложность следующей функции C равна (предположим, что n> 0 (GATE CS 2004)

int recursive (mt n)

{

   if (n == 1)

     return (1);

   else

     return (recursive (n-1) + recursive (n-1));

}

(A) 0 (n)
(B) 0 (нет)
(С) 0 (n ^ 2)
(D) 0 (2 ^ n)

Ответ: (Д)
Пояснение: Рекурсивное выражение для вышеуказанной программы будет.

  T(n) = 2T(n-1) + c
  T(1) = c1.

Позвольте нам решить это.

  T(n) = 2(2T(n-2) + c) + c        = 4T(n-2) + 3c
  T(n) = 8T(n-3) + 6c + c          =  8T(n-3) + 7c
  T(n) = 16T(n-4) + 14c + c        =  16T(n-4) + 15c
  ............................................................
  .............................................................
  T(n) = (2^(n-1))T(1) +  (2^(n-1) - 1)c

  T(n) = O(2^n)

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 9

0.00 (0%) 0 votes