Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 09 - Рандом + Геометрия (Сергей Копелиович)

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции "Рандом + Геометрия"

1. Offline RMQ за O((n+m)^*)
2. Пересечение полуплоскостей за O(N^2), O(NlogN)
3. Random-O(n)-algo
4. Факторизация числа за O(N^{1/4})
5. Наибольшая общая возрастающая ща O(N^2) и O(Nlog^2N)