|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Teterin 2:5020/400 31 Jul 2002 19:34:30
To : Dmitriy K.
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Хай, Дмитрий!
"Dmitriy K." <krylov@mail.primorye.ru>
<skipped>
Спасибо за ответ. Жаль, линейная сортировка нескольких миллионов 160-ти
разрядной информации по указанному алгоритму не получится - если выделять
старшие разряды, опять получится этот противный N*log(n) ;)
> P.S. А может, сразу отсортированную последовательность генерить?
Прикладное значение сего - быстрый поиск (быстрее log(n)) с использованием
хешей - хеши дают более-менее равномерное распределение.
....равномерное распределение дает интересное свойство - зная значение
элемента, мы можем примерно вычислить его положение после сортировки.
Hапример, при идеальном равномерном распределении 65536 16ти-разрядных чисел
положение каждого числа после сортировки будет равно его значению :) Ломаю
голову, пытаясь использовать это, написал алгоритм, но при малейшем
отклонении от равномерности опять всплывает этот противный логарифм :)
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
