Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 50

Алгоритм выполняет (logN) 1/2 операций поиска, N операций вставки, (logN) 1/2 операций удаления и (logN) 1/2 операций уменьшения ключа над набором элементов данных с ключами, взятыми из линейно упорядоченного набора , Для операции удаления предоставляется указатель на запись, которая должна быть удалена. Для операции нажатия клавиши указатель предоставляется на запись, у которой уменьшен ключ. Какая из следующих структур данных является наиболее подходящей для использования алгоритмом, если цель состоит в том, чтобы достичь наилучшей общей асимптотической сложности с учетом всех операций?
(A) Несортированный массив
(B) Мин-куча
(C) Сортированный массив
(D) отсортированный двусвязный список

Ответ: (А)
Объяснение: Временная сложность вставки в несортированный массив составляет O (1), O (Logn) в Min-Heap, O (n) в отсортированном массиве и отсортированной DLL.

  1. Для несортированного массива мы всегда можем вставить элемент в конец и сделать вставку за O (1) раз
  2. Для Min Heap вставка занимает O (Log n) время. За подробностями обращайтесь к операциям двоичной кучи .
  3. Для отсортированного массива вставка занимает O (n) времени, поскольку нам может потребоваться переместить все элементы в худшем случае.
  4. Для отсортированного двусвязного списка вставка занимает O (n) времени, чтобы найти позицию вставляемого элемента.

Поскольку число операций вставки асимптотически больше, предпочтительным является несортированный массив.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 50

0.00 (0%) 0 votes