Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Не так. Сортировка слиянием подразумевает один массив на... 11.12.06 00:21 Число просмотров: 3942
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> Обьясните, почему сложность сортировки слиянием N*log(N) ?
>
> Есть два отсортированных массива длинной X и Y
> соответственно. На каждом шаге алгоритма определеляет
> минимальный из двух минимальных элементов этих массиво,
> который идет в выходной масив, т.е. совершается максимум
> X+Y операций (меньше X+Y, если X != Y).
>
> Получается при условии, что входные массивы были
> упорядочены, сложность этого алгоритма N, но в литературе
> сложность определяется как N*log(N).
Не так. Сортировка слиянием подразумевает один массив на входе. Он делится на пары. Пары объединяются в 4-ки. И т д. Т.е. шагов около ln(Длина). На каждом шаге О(длина). Результат сложности - сумма сложностей на каждом шаге. Прочитайте еще разок алгоритм.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
Не так. Сортировка слиянием подразумевает один массив на... - MadBinom