|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Simontsev 2:5005/115.41 30 Oct 2001 13:38:40
To : Egorov Pavel
Subject : 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
Sunday, October 28 2001 23:45, Egorov Pavel wrote to Andrew Simontsev:
AS>> Имхо это как раз гарантии не дает, разве что распределение
AS>> какое-нибудь особое. Смысл всех этих хитростей - это выбор опорного
AS>> элемента, который бы делил массив на как можно более равные половины
AS>> (в идеале надо брать медиану, но это слишком "дорогостоящий"
AS>> алгоритм)...
EP> Медиана в смысле A[(l+r) div 2]?
Медиана - это n/2 порядковая статистика, т.е. элемент, который бы стоял
в центре отсортированного массива.
EP> Почему же тогда догоростоящий? ИМХО, "все одинаковые" (с)
Алгоритм k-той порядковой статистики слишком трудоемок, чтобы запихивать
его рекурсию или цикл. В принципе есть какой-то алгоритм, работающий за линейное
время, но его не применяют на практике, да и к тому же это слишком много...
Hужно выбирать опорный элемент за один шаг...
EP> Я мыслю так: Элемент можно брать хоть какой, по идее. Hо если брать
EP> какой-то определенный (медиану, например), то можно запросто придумать
EP> пример массива, который сортируется БЫСТРОСОРТОМ за квадрат.
Честно говоря сложно представить... Разве что какой-нибудь вырожденный
случай, когда все элементы одинаковы...
EP> Если внести элемент случайности - то никакой злоумышленник хитрый
EP> массив построить не сможет :)
Обычно массивы, которые надо сортировать, не злоумышленники придумывают,
а они сами по себе появляются (в смысле практически не зависимо от человека)
EP> Т.е. Хоть вероятность того, что БЫСТРОСОРТ отработает за квадрат
EP> и неуменьшилась, но теперь никто не сможет придумать контр примерчик
EP> на котором он тормозит.
Думаешь кто-то сидит и придумывает, как бы усложнить работу алгоритма?
Странный ты какой-то. Если в массиве данные распределены равномерно, то такое
поведение имхо однозначно не дает оптимальной работы алгоритма.
Квадрат-то появляется, если каждый раз ты будешь в качестве опорного
элемента брать минимум/максимум или приближенный к нему элемент. Если
распределение равномерно (а именно такое предположение делается, когда ничего не
известно о распределении данных), тогда ты с одинаковой вероятностью будешь
выбирать либо минимум/максимум либо середину, либо какой-нибудь другой элемент.
Поэтому наверняка в некоторых итерациях он будет достаточно долго работать...
Правда если вид распределения нормальный (т.е. Гаусс), то выбор элемента
наугад может давать хорошие результаты...
Bye, Egorov.
Sincerely yours, Andrew.
Играет симфония Глюка на клавиатуре :-)
... I'm a VooDoo Chile!
--- Добрых дел мастер 3.0.1 лет ----------------------------------
* Origin: Меняю комнатную собачку на двухкомнатную. (2:5005/115.41)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
