нет, наврал.. сортировка слиянием даже для отсортированного массива имеет нелинейную сложность29.06.06 13:35 Число просмотров: 4065 Автор: zelych Статус: Member
Обьясните, почему сложность сортировки слиянием 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
log(N) часто характеризует алгоритм, в котором присутствует разбивка на две части, далее разбивка этих частей еще на две и т.д. В этом случае кол-во разбивок будет равно двоичному логарифму от N, где N - размер исходного массива.
В алгоритме такой разбивки, как в qsort, нет. Откуда может взяться log(N) ?
это для упорядоченного массива29.06.06 13:32 Автор: zelych Статус: Member
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
