Рубрики

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

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

Рассмотрим следующее повторение:

Что из следующего верно?

(A) T (n) = (Loglogn)
(B) T (n) = (LOGN)
(C) T (n) = (SQRT (п))
(D) T (n) = (П)

(А) А
(Б) Б
(С) С
(D) D

Ответ: (Б)
Пояснение: Этот вопрос может быть решен сначала изменением переменной, а затем Master Method.

  Let n = 2^m
  T(2^m) = T(2^(m/2)) + 1
  Let T(2^m) =  S(m)
  S(m)  = 2S(m/2) + 1

Выше выражением является рекурсия обхода двоичного дерева, сложность времени (М). Вы также можете доказать, используя теорему мастера .

S(m)  = (m)  
      = (logn)  /* Since n = 2^m */

Теперь вернемся к исходной рекурсивной функции T (n).

  T(n)  = T(2^m) = S(m)
                 = (Logn)

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

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

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

0.00 (0%) 0 votes