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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
И действительно. Ведь зачем его сортировать, раз он уже... 11.12.06 00:22  Число просмотров: 3025
Автор: MadBinom Статус: Незарегистрированный пользователь
<"чистая" ссылка>
И действительно. Ведь зачем его сортировать, раз он уже отсортирован?
<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