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


Что: Лекция
Когда: Суббота, 14 октября 2017, 14:30–16:10
Где: НГУ, ауд. 2128
Слайды: algorithms_1_lecture_141017.pdf

Описание

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