наука и физика

Статьи

SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи GRA Алгоритм Алгоритм Джонсона Кратчайшие пути при отрицательных весах: потенциалы Беллмана — Форда, перевзвешивание и Дейкстра от каждой вершины. O(V·E + V·(V + E) log V) 2 задачи GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи GRA Алгоритм Тяжёлые пути Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков. O(log² n) на запрос 1 задача GRA Алгоритм Центроидная декомпозиция Делим дерево центроидами: log₂ n уровней, и ближайшая отмеченная вершина — за O(log n) после каждой отметки. O(log n) на отметку и на вопрос 1 задача DP Алгоритм Выравнивание последовательностей Лучшее сопоставление двух последовательностей с очками за замены и пропуски: целиком, по кускам и с проверкой на случайность. O(m · n) 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи RND Приём Случайные блуждания Шаг наугад на каждом перекрёстке: √t, время до цели, «кто первый» и 2-SAT случайным блужданием. O(1) на шаг 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи

Задачи

Блуждающий зуб Землетрясения в диапазоне Сколько выпало дождя Вдоль какой линии Где будет тело через время T Градусо-часы по датчику с пропусками Картотека в лотке Кластеры на карте эпицентров Когда потеплеет Место в каталоге Не больше R оповещений Повороты на конвейере Прогоны снегоочистителя Ровно ноль градусов Самый дальний бросок Самый жаркий день Сейсмическая тревога Сколько нужно залов Сопротивление цепи Сушь Толчки рядом во времени Три класса глубины Участки G и C Хроника из региональных каталогов Давление в центре планеты Индекс из прямых Медиана за окно Неявный шаг сквозь стену Поправки к ряду Сжать климат до k чисел Сколько соседей спросить о глубине Тёплые дни Уравнение Кеплера без осечек Экскурсия по дереву жизни Электромобиль в горах Медиана периода Описанный родственник Паводок Первый заморозок Сложность по Лемпелю — Зиву

Часто рядом

классика 24 собеседования 12 олимпиады 10 аналитика 9 массив 7 дерево 7 матрица 6 итерации 5 точность вычислений 5 в проде 5 граф 5 приближение 5