сортировка с линейной сложностью

From

Roman Kukushkin (2:5025/37.216)

To

Ilya Teterin

Date

2002-08-01T21:08:35Z

Area

RU.ALGORITHMS

Как поживаете, Ilya ?

 Среда Июль 31 2002 в 19:34 Ilya Teterin писал Dmitriy K.:


 >> P.S. А может, сразу отсортированную последовательность генерить?
 IT> Прикладное значение сего - быстрый поиск (быстрее log(n)) с
 IT> использованием хешей - хеши дают более-менее равномерное
 IT> распределение.

 IT> ....равномерное распределение дает интересное свойство - зная значение
 IT> элемента, мы можем примерно вычислить его положение после сортировки.
 IT> Например, при идеальном равномерном распределении 65536 16ти-разрядных
 IT> чисел положение каждого числа после сортировки будет равно его
 IT> значению :) Ломаю голову, пытаясь использовать это, написал алгоритм,
 IT> но при малейшем отклонении от равномерности опять всплывает этот
 IT> противный логарифм :)
А какого рода отклонение от равномерности? Распределение известно?

                C уважением, Roman Kukushkin.

E-mail krv@vudor.vrn.ru

---
 * Origin:  (2:5025/37.216)