Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 22

Обычная реализация ser (n 2 ) Insertion Sort для сортировки массива использует линейный поиск для определения позиции, в которой элемент должен быть вставлен в уже отсортированную часть массива. Если вместо этого мы используем бинарный поиск для определения позиции, наихудшее время выполнения

1)
2)
3)
стать Θ (n log n)
4) стать Θ (n)
(A) остаются Θ (n 2 )
(B) стать Θ (n (log n) 2 )
(C) стать Θ (n log n)
(D) стать Θ (n)

Ответ: (А)
Пояснение: см. Вопрос 1 из http://espressocode.top/data-structures-and-algorithms-set-6/

Также см. Бинарная сортировка вставок

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 22

0.00 (0%) 0 votes