|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Egorov Pavel 2:5080/169.35 29 Oct 2001 00:45:12
To : Andrew Simontsev
Subject : 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
On Friday October 26 2001 you wrote to Egorov Pavel:
AE>>>> В лучшем случае действительно превосходит. Hо вот только быстрая
AE>>>> сортировка очень сильно зависит от входных данных (можем получить и
AE>>>> O(N*ln(N)) и O(N*N)), а в пирамидальной худшего случая не бывает -
AE>>>> всегда O(N*ln(N)).
AS>>> Вроде бы есть какие-то хитрости, которые исключают худший
AS>>> случай (какой-то особо хитрый выбор медианы).
EP>> Random называется :)
AS> Имхо это как раз гарантии не дает, разве что распределение
AS> какое-нибудь особое. Смысл всех этих хитростей - это выбор опорного
AS> элемента, который бы делил массив на как можно более равные половины (в
AS> идеале надо брать медиану, но это слишком "дорогостоящий" алгоритм)...
Медиана в смысле A[(l+r) div 2]?
Почему же тогда догоростоящий? ИМХО, "все одинаковые" (с)
Я мыслю так: Элемент можно брать хоть какой, по идее. Hо если брать какой-то
определенный (медиану, например), то можно запросто придумать пример массива,
который сортируется БЫСТРОСОРТОМ за квадрат. Если внести элемент случайности -
то никакой злоумышленник хитрый массив построить не сможет :)
Т.е. Хоть вероятность того, что БЫСТРОСОРТ отработает за квадрат и
неуменьшилась, но теперь никто не сможет придумать контр примерчик на котором он
тормозит.
Hу, Все! Пока Andrew.
--- GoldED/386 3.00.Alpha3+
* Origin: 2+2=4 это не тождество, а выражение равное TRUE (2:5080/169.35)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
