ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Khovayko [SPAM trap - don't re  2:5020/400     07 Aug 2003  01:55:58
 To : Nick Ignatov
 Subject : Re: n*log(n)
 -------------------------------------------------------------------------------- 
 

 Nick Ignatov wrote:
 
 > утвеpждения. Подскажите, плиз, как это можно обосновать. В кpайнем случае
 > ткните в ссылку в инете.
 
 Обосновывается так:
 
 Допустим, у нас есть неупорядоченый (даже частично)
 массив (или иная структура из N) элементов.
 Их надо отсортировать, то есть произвести перестановку.
 Эту перестановку можно рассматривать как операцию типа:
 
   - для каждого элемента входного массива
   -- поместить его в правильную позицию выходного массива.
 
 Hомер этой правильной позиции совершенно неизвестен заранее.
 Этот номер можно рассматривать как X-битовое
 двоичное число, где X - двоичный логарифм от N.
 Если у нас есть только операция сравнения больше/меньше,
 что бы с чем не сравнивать - все равно одно сравнение
 даст максимум один бит информации.
 Чтобы однозначно определить выходную позицию конкретного
 элемента, нужно заполнить X битов его новой позиции,
 то есть провесть X сравнений.
 То есть для одного элемента надо провести Log2(N) сравнений.
 
 Всего таких элементов у нас N.
 
 Вот и получается N*Log2(N).
 
 -- 
 #include <best/regards>
 Oleg Khovayko  http://olegh.spedia.net
 PS/ATTN: Reply to reverted address net.comcast@olegh
 
 --- ifmail v.2.15dev5
  * Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор