Рубрики

Структуры данных | Куча | Вопрос 1

Какова временная сложность операции Build Heap. Build Heap используется для построения максимальной (или минимальной) двоичной кучи из заданного массива. Сборка кучи используется в сортировке кучи в качестве первого шага для сортировки.
(A) O (nLogn)
(B) O (n ^ 2)
(C) O (Logn)
(D) O (n)

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

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

Хотя сложность в худшем случае выглядит как O (nLogn), верхняя граница сложности времени — O (n). Смотрите следующие ссылки для доказательства сложности времени.

Время Сложность построения кучи
Тест на этот вопрос

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

Структуры данных | Куча | Вопрос 1

0.00 (0%) 0 votes