Известные примеры идеи квадратного корня в анализе сложности

k = $\max \left\{k, n/k\right\}$$k=\sqrt n$

• алгоритм гигантского шага baby-step для вычисления дискретного логарифма в $O(\sqrt n)$ ,
• статический двухмерный ортогональный отсчет во времени $O(\sqrt n)$ и памяти $O(n)$ ,
• приоритетная очередь с EXTRACT-MIN в $O(\sqrt[k] n)$ и DECREASE-KEY в $O(1)$ ,
• раскрасить трехцветный граф $O(\sqrt n)$ цветами за полиномиальное время,

Просто назвать несколько.

Хотя такие алгоритмы часто бывают неоптимальными, их легко понять студентам и хорошо показать, что наивные границы не являются оптимальными. Кроме того, структуры данных с квадратным корнем иногда более практичны, чем их аналоги на основе бинарного дерева, из-за удобства работы с кешем (без учета методов, не обращающих внимания на кеш). Вот почему я уделяю немного внимания этой теме во время обучения.

Мне интересны более характерные примеры такого рода. Поэтому я ищу любые (желательно элегантные) алгоритмы, структуры данных, протоколы связи и т. Д., Анализ которых основан на идее квадратного корня. Их асимптотика не должна быть оптимальной.

Chazelle, Liu и Magen в статье « Сублинейные геометрические алгоритмы» (STOC 2003, SICOMP 2006) имеют несколько умных применений следующего трюка со случайной выборкой. Вариации того же трюка ранее использовались Gärtner и Welzl [ DCG 2001 ], которые ссылаются на первое издание CLR (1990).

Предположим, нам дан отсортированный круговой связанный список чисел, хранящийся в непрерывном блоке памяти. То есть у нас есть два массива и , гдеN e x t [ 1 .. n $Key[1..n]$$Next[1..n]$

• $Key[1..n]$ хранит набор из чисел в произвольном порядке;$n$
• Если является наибольшим числом в наборе, то является наименьшим числом в наборе; в противном случае - это наименьшее число в наборе, которое больше чем .К е у [ Н е х т [ я ] ] К е у [ Н е х т [ я ] ] К е у [ я $Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Затем мы можем найти преемника данного числа в ожидаемом времени следующим образом:O ( $x$$O(\sqrt{n})$

• Выберите случайную выборку элементов массива . Пусть будет самой большой выборкой, которая меньше (или самой большой выборкой, если все выборки больше ). KeyKey[j]x$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Следуйте указателям из пока мы не увидим число, большее или равное (после переноса, если все выборки были больше ).K e y [ j ] x $Next$$Key[j]$$x$$x$

Относительно простое применение леммы Яо подразумевает, что ожидаемая граница времени является оптимальной. Любой детерминированный алгоритм для этой задачи требует времени в худшем случае.Ω(n$O(\sqrt{n})$$\Omega(n)$

В любом графе граней есть треугольников, и их можно найти за времени. Есть много способов сделать это, но я думаю, что одним из первых является Itai и Rodeh (STOC 1977), которые предоставляют алгоритм, который проходит через последовательность итераций линейного времени, каждая из которых удаляет остовный лес из графа. На ранних итерациях, когда оставшийся лес имеет не менее компонентов, алгоритм удаляет не менее ребер за шаг, а на поздних итерациях, когда он имеет не более компонентов, максимальная степень равна и уменьшается как минимум на одну в каждом шаг. Таким образом, общее количество итераций не болеем O ( м 3 / 2 ) п - к к п - к к м / к + к О ( $O(m^{3/2})$$m$$O(m^{3/2})$$n-k$$k$$n-k$$k$$m/k+k$ и выбор правильного компромисса дает общую оценку на итерации и по времени.O(м 3 / 2$O(\sqrt m)$$O(m^{3/2})$