5. Порядковые статистики
Суббота, 14 октября 2017
НГУ, ауд. 2128, НГУ, новый корпус
Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск от края
(galloping).
Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае.