|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Val Krigan 2:5020/400 08 Apr 2003 00:45:16
To : Vladislav Gusev
Subject : Re: Сортировка
--------------------------------------------------------------------------------
"Vladislav Gusev" wrote
> Оносновное достоинство метода сортировки, описанного автором исходного письма
> это сложность - O(n). Твой первый вариант напоминает HeapSort, второй
> даже не знаю что. :) И чем они лучше общеизвестных алгоритмов сортировки мне
> не понятно. Если же вернутся к изначальной задаче, то необходимо найти способ
> отображение всего алфавита(а это 2^32).
> Hа x86 для этого в любом случаи не хватит адресного пространства.
Основная проблема - по числу найти счетчик встречаемости. Считаем, возможно лишь
ограниченое кол-во этих значений. От этого и пляшем.
В оригинальном алгоритме счетчик легко находился в массиве по порядковому
номеру.
В предложенных мною этот поиск делался или в уравновешенном дереве, или в
хеш-таблице.
В оригинале пересортировка не нужна, поскольку счетчики в массиве уже
отсортированы.
В моих - в случае дерева пересортировка не нужна, дерево уже отсортировано.
Сложность O(N * log(M)). Где N - размер исходного массива, M - размер алфавита
(множества значений). Если М константа, то в итоге O(N).
В случае хеша нужна пересортировка. Сложность 1 фазы O(N), заполнение
хеш-таблицы, один проход. Сложность второй фазы O(M * loh(M)), сортировка.
ОБщая сложность O(N)? Если алфавит задан заранее, то и отсортировать его тоже
можно заранее.
Естественно эти алгоритмы можно использовать не только для чисел с плавающей
точкой, но и для любых австрактных объектов которые а) можно сравнивать на
больше меньше, б) множество значений которых ограничено. Для второго метода
необходима возможносто построения хеш-функции.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
