Задачник Базовый курс EN

Что решает

k-я статистика

Статьи

SRT Приём Нижние границы сравнений Почему нельзя быстрее: подсчёт исходов и игра против судьи; сортировка, второй в турнире, минимум с максимумом, слияние. сортировка — ⌈log₂ n!⌉ сравнений 1 задача SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи DS Структура данных Персистентные структуры Каждое изменение — новая версия, старые живы; копируется только путь от корня. Медиана любого периода — разность двух версий. O(log n) на изменение и запрос 1 задача DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи

Задачи

Склад на сетке улиц Медиана периода

Часто рядом

классика 5 собеседования 5 сортировка 2 разделяй и властвуй 2 в проде 2 базы данных 2 запросы на отрезке 2 олимпиады 2 оценка 1 случайность 1 на месте 1 аналитика 1