ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Goldobin                     2:5020/400     14 Jul 2003  11:11:36
 To : Nick Ignatov
 Subject : Re: QuickSort
 -------------------------------------------------------------------------------- 
 

 Hi!
 
 > Расскажите, плиз, как математически выводится эффективность сабжа (т.е.
 > nlogn), как (опять же, математически) получить _точный_ (или
 
 Если ничего неизвестно о сортируемых данных, то выбор среднего значения для
 каждого из интервалов случаен и может в худшем случае привести к N итерациям
 вместо logN. Так что NlogN - это если повезет или если есть дополнительная
 информация о сортируемых данных, позволяющая вычислить среднее значение. А
 так от NlogN до N^2/2, куда статистически ближе зависит от распределения
 данных и метода выбора среднего.
 
 > почти точный) необходимый под итеpационный его ваpиант pазмеp стека (для
 > хpанения гpаниц pазбиения). "Точный" значит, что ваpиант log(n) не
 
 подходит,
 
 > поскольку память под стек выделяется заpанее, а бpать с запасом (особенно,
 > большим) не хочется.
 
 Делать полурекурсивный метод - рекурсивно спускаться по более короткой
 ветке, а более длинную оставлять обрабатывать в общем цикле. В этом случае
 logN - это точное значение глубины рекурсии, поскольку при каждом спуске
 количество данных гарантированно сокращается более чем вдвое либо ровно
 вдвое. Используешь ли ты рекурсивный вызов или складируешь границы в
 собственном стеке - сути не меняет, начинай обрабатывать с более короткой
 ветки.
 
 Bye.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 11:11:36   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 12:49:13   Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 13:01:15   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 13:34:27   Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 13:59:47   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 15:50:02