Рубрики

Структуры данных | Связанный список | Вопрос 4

Какой из следующих алгоритмов сортировки можно использовать для сортировки случайного связанного списка с минимальной временной сложностью?
(A) Сортировка вставки
(B) Быстрая сортировка
(C) Сортировка кучи
(D) Слияние сортировки

Ответ: (Д)
Объяснение: Сортировка слиянием и сортировка вставкой могут использоваться для связанных списков.

Медленная производительность произвольного доступа связанного списка делает другие алгоритмы (такие как быстрая сортировка) плохо работающими, а другие (такие как heapsort) совершенно невозможными.

Поскольку временная сложность сортировки слиянием в худшем случае равна O (nLogn), а сортировка вставки — O (n ^ 2), сортировка слиянием предпочтительна.

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

Структуры данных | Связанный список | Вопрос 4

0.00 (0%) 0 votes