Лекция 5. Порядковые статистики

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