случайность

SRT Алгоритм Быстрая сортировка Разбиение вокруг опорного: в среднем n log n на месте, в худшем n² — и как от худшего защищаются. O(n log n) 2 задачи SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача DS Структура данных Хеширование кукушки Два гнезда на ключ, поиск — не больше двух проб; вставка выселяет жильцов. Работает до заполнения 1/2, с корзинами — до 98 %. поиск — не больше d проб в худшем; вставка — O(1) в среднем ниже порога 1 задача DS Структура данных Верёвка Текст кусками в листьях дерева: вставка и удаление в середине — путь к листу и один кусок; номер строки — по счётчикам в узлах. O(log n + C) на вставку, удаление, доступ 1 задача DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи NUM Алгоритм ρ-алгоритм Полларда Делитель p числа n за ~√p шагов: цикл по модулю неизвестного p, черепаха и заяц, НОД. O(√p) умножений по модулю n 1 задача GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи SYS Алгоритм Raft Реплицированный журнал на ненадёжных серверах: лидер, сроки, большинство; выдерживает падение меньшей половины. один круг сообщений до большинства на запись 2 задачи SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи RND Приём Лас-Вегас и Монте-Карло Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое. O(k · стоимость одной попытки) 2 задачи RND Приём Случайные блуждания Шаг наугад на каждом перекрёстке: √t, время до цели, «кто первый» и 2-SAT случайным блужданием. O(1) на шаг 2 задачи RND Алгоритм Имитация отжига Локальный поиск, который принимает ухудшения с вероятностью e^(−Δ/T) и постепенно остывает. O(S · c) 2 задачи RND Алгоритм Генетический алгоритм Популяция решений, отбор, скрещивание и мутация: эволюция траектории на настоящем автодроме. O(G · N · c) 2 задачи