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

Что решает

ближайший сосед

Статьи

SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи STR Структура данных BK-дерево Все пароли в одной-двух правках от данного: неравенство треугольника отрезает целые ветви — и где оно перестаёт помогать. O(N · глубина) на построение 1 задача PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача GEO Структура данных R-дерево Окно карты 10° × 5°: из 58 987 отрезков берега R-дерево проверяет 847 прямоугольников. И находит город, дальше всех от моря. окно — число открытых узлов × M; ближайший — обычно O(log n) узлов 1 задача ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи

Задачи

Ближайший цвет палитры Район по соседям Пары ближе r Ближайшие города Где поставить новую часть Два ближайших города Сколько соседей спросить о глубине Соседи пароля

Часто рядом

геоданные 6 точки на плоскости 5 классика 5 собеседования 4 карты и навигация 4 дерево 3 куча 2 базы данных 2 разделяй и властвуй 2 случайность 2 хеширование 2 аналитика 2