Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 85

GATE

Программа принимает в качестве входных данных сбалансированное двоичное дерево поиска с n конечными узлами и вычисляет значение функции g (x) для каждого узла x. Если стоимость вычисления g (x) составляет минимум {нет. листовых узлов в левом поддереве x, нет. листовых узлов в правом поддереве x}, тогда временная сложность программы в худшем случае
(A) Θ (n)
(B) Θ (nLogn)
(C) Θ (n 2 )
(D) Θ (n 2 log n)

Ответ: (Б)
Объяснение:

The recurrence relation for the recursive function is
T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
     = 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n))

Источник: http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2004 | Вопрос 85

0.00 (0%) 0 votes