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


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

Описание

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

Видео