Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 53

Массив целых чисел размера n можно преобразовать в кучу, отрегулировав кучи, укорененные в каждом внутреннем узле полного двоичного дерева, начиная с узла ⌊ (n — 1) / 2⌋, и выполнив эту настройку вплоть до корневого узла (корневой узел имеет индекс 0) в следующем порядке: n (n — 1) / 2⌋, ⌊ (n — 3) / 2⌋,… .., 0. Время, необходимое для построения кучи таким образом, составляет
(A) O (log n)
(B) O (n)
(С) O (n log log n)
(D) O (n log n)

Ответ: (Б)
Объяснение: Приведенный выше оператор фактически является алгоритмом для построения кучи входного массива A.

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Верхняя граница сложности времени O (n) для вышеупомянутого алгоритма

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

ВОРОТА | GATE-IT-2004 | Вопрос 53

0.00 (0%) 0 votes