Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Сложность сортировки слиянием 29.06.06 10:02
Автор: makeworld Статус: Member
Отредактировано 29.06.06 10:02 Количество правок: 1
|
Обьясните, почему сложность сортировки слиянием N*log(N) ?
Есть два отсортированных массива длинной X и Y соответственно. На каждом шаге алгоритма определеляет минимальный из двух минимальных элементов этих массиво, который идет в выходной масив, т.е. совершается максимум X+Y операций (меньше X+Y, если X != Y).
Получается при условии, что входные массивы были упорядочены, сложность этого алгоритма N, но в литературе сложность определяется как N*log(N).
|
|
Не так. Сортировка слиянием подразумевает один массив на... 11.12.06 00:21
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> Обьясните, почему сложность сортировки слиянием N*log(N) ?
>
> Есть два отсортированных массива длинной X и Y
> соответственно. На каждом шаге алгоритма определеляет
> минимальный из двух минимальных элементов этих массиво,
> который идет в выходной масив, т.е. совершается максимум
> X+Y операций (меньше X+Y, если X != Y).
>
> Получается при условии, что входные массивы были
> упорядочены, сложность этого алгоритма N, но в литературе
> сложность определяется как N*log(N).
Не так. Сортировка слиянием подразумевает один массив на входе. Он делится на пары. Пары объединяются в 4-ки. И т д. Т.е. шагов около ln(Длина). На каждом шаге О(длина). Результат сложности - сумма сложностей на каждом шаге. Прочитайте еще разок алгоритм.
|
|
там наверное написано О(N*log(N)), а буква О обозначает... 29.06.06 13:13
Автор: zelych Статус: Member
|
> Получается при условии, что входные массивы были
> упорядочены, сложность этого алгоритма N, но в литературе
> сложность определяется как N*log(N).
там наверное написано О(N*log(N)), а буква О обозначает верхнюю границу сложности..
кажется так
|
| |
ну так, по моему, N и есть верхняя граница. 29.06.06 13:29
Автор: makeworld Статус: Member
Отредактировано 29.06.06 13:35 Количество правок: 2
|
log(N) часто характеризует алгоритм, в котором присутствует разбивка на две части, далее разбивка этих частей еще на две и т.д. В этом случае кол-во разбивок будет равно двоичному логарифму от N, где N - размер исходного массива.
В алгоритме такой разбивки, как в qsort, нет. Откуда может взяться log(N) ?
|
| | |
это для упорядоченного массива 29.06.06 13:32
Автор: zelych Статус: Member
|
|
|
| | | |
нет, наврал.. сортировка слиянием даже для отсортированного массива имеет нелинейную сложность 29.06.06 13:35
Автор: zelych Статус: Member
|
|
|
| | | | |
И действительно. Ведь зачем его сортировать, раз он уже... 11.12.06 00:22
Автор: MadBinom Статус: Незарегистрированный пользователь
|
|
И действительно. Ведь зачем его сортировать, раз он уже отсортирован?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
