Семинар 2. Разное

Пятница, 17 сентября 2021
НГУ, ауд. 3122, НГУ, новый корпус

Описание

Долг: Задача поиска для каждого элемента массива ближайшего элемента слева, меньшего его. Решение со стеком за O(N).

Два указателя. Поиск самого длинного подотрезка с суммой не более M. Основное свойство: R*(L+1) >= R*(L). Алгоритм и анализ сложности O(N).

Оценка практического быстродействия программы. Тактовая частота и кол-во операций в секунду. Оценка адекватности асимптотики по ограничениям.

Бинарный поиск. Вещественный и дискретный варианты. Тонкости реализации на примере std::lower_bound. Использование полуоткрытого интервала. Бинарный поиск по ответу. Нахождение самого длинного подотрезка за O(N log N): бин. поиск и преф. суммы.

Не успели: Обработка событий. Задача о поиске точки, принадлежащей максимальному кол-ву отрезков из заданного множества. Решение за O(N log N). Тонкости реализации (совпадающие события).