ru.algorithms

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

 > > А почему NlogN? худший вариант использования стека для быстрой
 > сортировки -
 > > просто N.
 >
 > Это про эффективность самой сортировки.
 
 худший случай для быстрой сортировки - N^2, однако матожидание близко к N
 
 > А максимальная глубина стека в
 > худшем случае не N, а logN если первыми начинать обрабатывать всегда более
 > короткие ветки, а по более длинной не спускаться, а обрабатывать на том же
 > уровне.
 
 Представьте худший вариант - Вы всегда выбираете элемент, который является
 минимальным (считаем, что сортируем в порядке возрастания) - тогда
 использование стека N.
 
 > > А почему Вы не используете стандартную функцию STL? она _очень_
 
 эффективна
 
 > > практически для любых данных (кроме строк и данных с малым диапазоном
 > > значений).
 >
 > Hаверное что-то специфическое с большими ограничениями на память. Да и
 > вообще в частных случаях, когда тебе о данных известно нечто, чего не
 > учитывает универсальный алгоритм, можно сделать быстрее.
 
 :-)) попробуйте, я выиграл у 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