Лекция 5. Порядковые статистики (Алгоритмы и структуры данных, часть 1)

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

Лекция №5 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов