поиск

SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Экспоненциальный поиск Шаги 1, 2, 4, 8, … пока не перескочишь, потом двоичный поиск: когда граница неизвестна или ответ близко. 2⌊log₂ i⌋ + 1 вопрос до позиции i 1 задача SRT Алгоритм Интерполяционный поиск Прикинуть место по значениям на краях: log log n проб на равномерных ключах и до n — на неудобных. ≈ log₂ log₂ n в среднем, n в худшем 1 задача SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача DS Структура данных B-дерево Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц. O(log n) сравнений, O(log_B n) чтений страниц 2 задачи DS Структура данных Косое дерево После каждого запроса ключ поднимается в корень парами поворотов: частые ключи сами собираются наверху, амортизированно O(log n). O(log n) амортизированно на операцию; одна операция — до O(n) 1 задача DS Структура данных Бор (префиксное дерево) Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса. O(L) на вставку и поиск слова длины L 2 задачи STR Алгоритм Наивный поиск подстроки Образец прикладывают к каждой позиции текста: n · m сравнений в худшем случае, около n — на обычном тексте. O(n · m) 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи