информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Очередное исследование 19 миллиардов... 
 Оптимизация ввода-вывода как инструмент... 
 Зловреды выбирают Lisp и Delphi 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
если вы видите этот текст, отключите в настройках форума использование JavaScript
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
нет, наврал.. сортировка слиянием даже для отсортированного массива имеет нелинейную сложность 29.06.06 13:35  Число просмотров: 4055
Автор: zelych Статус: Member
<"чистая" ссылка>
<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-2025 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach