Re: Quick Sort

From

Sergey Andrianov (2:5020/1507.400)

To

Nickita A Startcev ()

Date

2003-02-25T20:59:42Z

Area

RU.ALGORITHMS

Здравствуй, Nickita!

Однажды 25-Feb-03  в 03:10   Nickita A Startcev (2:5030/1039.8)
написал       Alexy Medveschek    по поводу
-=-   Quick Sort  -=-

SS>>>>>> Доказательство говорит, что быстрее, чем O(NlogN) не бывает.
AM>>         ^^^^^^^^^^^^^^
AM>>      Прошу прощения, что влез в разговор (тем более так "вовремя" ;),
AM>> но на моей памяти не встречалось этого доказательства, и даже напротив
AM>> говорилось о невозможности доказать, что не существует алгоритмов
AM>> порядка приближенного к N.
AM>>      Если таковое и правда есть, то где можно посмотреть (доки,
AM>> URL...).

NAS> Таблица из 2^N элементов (где N - число разрядов в сортируемых данных) 
NAS> даст линейное время сортировки.

	Это - частный случай, а здесь рассматривается общий.

                  До свидания,  в  20:59 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)