Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Сложность сортировки слиянием 29.06.06 10:02 Число просмотров: 5555
Автор: makeworld Статус: Member Отредактировано 29.06.06 10:02 Количество правок: 1
|
Обьясните, почему сложность сортировки слиянием N*log(N) ?
Есть два отсортированных массива длинной X и Y соответственно. На каждом шаге алгоритма определеляет минимальный из двух минимальных элементов этих массиво, который идет в выходной масив, т.е. совершается максимум X+Y операций (меньше X+Y, если X != Y).
Получается при условии, что входные массивы были упорядочены, сложность этого алгоритма N, но в литературе сложность определяется как N*log(N).
|
- Сложность сортировки слиянием - makeworld 29.06.06 10:02 [5555]
|
|
|