Семинар 2. Разное (Алгоритмы и структуры данных, часть 1)

Задача о поддержании динамического максимума в стеке. Два указателя. Поиск самого длинного подотрезка с суммой не более M. Основное свойство: R*(L 1) больше/= R*(L). Алгоритм и анализ сложности O(N). Оценка практического быстродействия программы. Тактовая частота и кол-во операций в секунду. Оценка адекватности асимптотики по ограничениям. Бинарный поиск. Вещественный и дискретный варианты. Тонкости реализации на примере std::lower_bound. Использование полуоткрытого интервала. Бинарный поиск по ответу. Нахождение самого длинного подотрезка за O(N log N): бин. поиск и преф. суммы. Обработка событий. Задача о поиске точки, принадлежащей максимальному кол-ву отрезков из заданного множества. Решение за O(N log N). Тонкости реализации (совпадающие события). Семинар №2 в курсе “Алгоритмы и структуры данных, часть 1“, осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница семинара на сайте CS центра: Все видео курса по порядку: