Рубрики

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

Алгоритмы Задачи

Какова временная сложность следующей рекурсивной функции:

int DoSomething (int n) 

{

  if (n <= 2)

    return 1;

  else  

    return (DoSomething (floor(sqrt(n))) + n);

}

(А) (П)
(В) (NlogN)
(С) (LOGN)
(D) (Loglogn)
(А) А
(Б) Б
(С) С
(D) D

Ответ: (Д)
Объяснение: Рекурсивное отношение для DoSomething ()

  T(n) =  T() + C1 if n > 2

Мы проигнорировали часть floor (), так как здесь не имеет значения, пол это или потолок.

  Let n = 2^m,  T(n) = T(2^m)
  Let T(2^m) =  S(m)

  From the above two, T(n) = S(m)

  S(m) = S(m/2) + C1  /* This is simply binary search recursion*/
  S(m)  = O(logm)      
          = O(loglogn)  /* Since n = 2^m */
  
  Now, let us go back to the original recursive function T(n) 
  T(n)  = S(m) 
          = O(LogLogn)

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

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

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

0.00 (0%) 0 votes