аналитика

SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи