Рубрики

Алгоритмы | Сортировка | Вопрос 12

Какова наихудшая временная сложность сортировки вставки, когда позиция данных для вставки вычисляется с использованием бинарного поиска?

(А) Н
(B) NlogN
(С) N ^ 2
(D) N (logN) ^ 2

Ответ: (с)
Объяснение: Применение бинарного поиска для вычисления позиции данных, которые нужно вставить, не уменьшает временную сложность сортировки при вставке. Это связано с тем, что вставка данных в соответствующую позицию включает два этапа:
1. Рассчитайте позицию.
2. Сдвиньте данные из позиции, рассчитанной на шаге 1, на один шаг вправо, чтобы создать промежуток, в который будут вставлены данные.

Использование бинарного поиска уменьшает временную сложность на шаге 1 с O (N) до O (logN). Но временная сложность на шаге № 2 все еще остается O (N). Таким образом, общая сложность остается O (N ^ 2).
Тест на этот вопрос

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

Алгоритмы | Сортировка | Вопрос 12

0.00 (0%) 0 votes