ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Iassenev                     2:5020/400     14 Jul 2003  12:49:13
 To : Dmitriy Goldobin
 Subject : Re: QuickSort
 -------------------------------------------------------------------------------- 
 

 > > Расскажите, плиз, как математически выводится эффективность сабжа (т.е.
 > > nlogn), как (опять же, математически) получить _точный_ (или
 >
 > Если ничего неизвестно о сортируемых данных, то выбор среднего значения
 
 для
 
 > каждого из интервалов случаен и может в худшем случае привести к N
 
 итерациям
 
 > вместо logN. Так что NlogN - это если повезет или если есть дополнительная
 > информация о сортируемых данных, позволяющая вычислить среднее значение. А
 > так от NlogN до N^2/2, куда статистически ближе зависит от распределения
 > данных и метода выбора среднего.
 
 А почему NlogN? худший вариант использования стека для быстрой сортировки -
 просто N.
 
 А почему Вы не используете стандартную функцию STL? она _очень_ эффективна
 практически для любых данных (кроме строк и данных с малым диапазоном
 значений).
 
 С уважением,
 Дмитрий Ясенев.
 --- ifmail v.2.15dev5
  * Origin: Unknown (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