Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://lib.mexmat.ru/books/9165
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 09:04:46 2016
Кодировка: Windows-1251
Электронная библиотека Попечительского совета механико-математического факультета Московского государственного университета
Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Probabilistic analysis of some searching and sorting algorithms
Автор: Lent J.
Аннотация:
We use binary trees to analyze two algorithms, insertion sort and multiple quckselect. In each case, we consider the number of comparisons consumed as a measure of performance. We assume that the ranks of the n data values being searched or sorted form a random permutation of the integers {l,...,n}. For insertion sort, we consider the limiting distribution of the number of comparisons consumed in the process of sorting the n keys. We present an average-case analysis of the number of comparisons multiple qukkselect (MQS) requires for simultaneously finding several order statistics in the data set.