Рубрики

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

Какова ценность следующего повторения.


T(n) = T(n/4) + T(n/2) + cn2
T(1) = c
T(0) = 0

Где с — положительная постоянная

(A) O (n 3 )
(B) O (n 2 )
(С) O (n 2 Logn)
(D) O (nLogn)

Ответ: (Б)
Объяснение: Ниже приведено исходное дерево рекурсии для данного рекуррентного отношения.

           cn^2
         /      \
     T(n/4)     T(n/2)

Если мы далее разбиваем выражения T (n / 4) и T (n / 2), мы получаем следующее дерево рекурсии.

               cn^2
           /           \      
       c (n^2)/16       c(n^2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 

Разрушение дальше дает нам следующее

                 cn^2
            /             \      
       c(n^2)/16           c(n^2)/4
       /      \            /      \
c(n^2)/256  c(n^2)/64  c(n^2)/64    c(n^2)/16
 /    \      /    \    /    \         /    \    
 

Чтобы узнать значение T (n), нам нужно рассчитать сумму узлов дерева уровень за уровнем. Если мы суммируем вышеупомянутый уровень дерева по уровню, мы получим следующий ряд
T (n) = c (n ^ 2 + 5 (n ^ 2) / 16 + 25 (n ^ 2) / 256) +….
Вышеуказанная серия является геометрической прогрессией с соотношением 5/16
Чтобы получить верхнюю оценку, мы можем суммировать вышеуказанный ряд для бесконечных членов. Мы получаем сумму как (n ^ 2) / (1 — 5/16), которая является O (n ^ 2)

Обратитесь к следующей видео лекции для более подробной информации.
http://www.youtube.com/watch?v=whjt_N9uYFI

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

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

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

0.00 (0%) 0 votes