информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыЗа кого нас держат?Все любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
 Рекордное число уязвимостей в 2021 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





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




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach