Термины O (log log n) могут появляться во множестве разных мест, но обычно есть два основных маршрута, которые прибывают в эту среду выполнения.
Уменьшение квадратным корнем
Как упоминалось в ответе на связанный вопрос, общий способ для алгоритма иметь временную сложность O (log n) состоит в том, чтобы этот алгоритм работал, многократно уменьшая размер входных данных на некоторый постоянный коэффициент на каждой итерации. В этом случае алгоритм должен завершиться после O (log n) итераций, потому что после выполнения O (log n) делений на константу алгоритм должен уменьшить размер проблемы до 0 или 1. Вот почему, например, , двоичный поиск имеет сложность O (log n).
Интересно, что существует аналогичный способ уменьшения размера проблемы, который дает время выполнения в форме O (log log n). Что произойдет, если вместо разделения ввода пополам на каждом слое мы извлечем квадратный корень из размера на каждом слое?
Например, возьмем число 65 536. Сколько раз нам нужно разделить это на 2, пока мы не дойдем до 1? Если мы это сделаем, мы получим
- 65 536/2 = 32 768
- 32 768/2 = 16 384
- 16 384/2 = 8 192
- 8192/2 = 4096
- 4096/2 = 2048
- 2,048 / 2 = 1,024
- 1,024 / 2 = 512
- 512/2 = 256
- 256/2 = 128
- 128/2 = 64
- 64/2 = 32
- 32/2 = 16
- 16/2 = 8
- 8/2 = 4
- 4/2 = 2
- 2/2 = 1
Этот процесс занимает 16 шагов, и также бывает, что 65 536 = 2 16 .
Но если мы извлечем квадратный корень на каждом уровне, мы получим
- √65,536 = 256
- √256 = 16
- √16 = 4
- √4 = 2
Обратите внимание, что нужно всего четыре шага, чтобы полностью опуститься до 2. Почему?
Во-первых, интуитивное объяснение. Сколько цифр в числах n и √n? В числе n примерно log n цифр, а в √n примерно log (√n) = log (n 1/2 ) = (1/2) log n цифр. Это означает, что каждый раз, когда вы извлекаете квадратный корень, вы примерно вдвое уменьшаете количество цифр в числе. Поскольку вы можете только вдвое уменьшить количество k O (log k) раз, прежде чем оно упадет до константы (скажем, 2), это означает, что вы можете взять квадратный корень только O (log log n) раз, прежде чем уменьшите число. до некоторой константы (скажем, 2).
Теперь давайте подумаем, чтобы сделать это точным. Давайте перепишем приведенную выше последовательность в терминах степени двойки:
- √65,536 = √2 16 = (2 16 ) 1/2 = 2 8 = 256
- √256 = √2 8 = (2 8 ) 1/2 = 2 4 = 16
- √16 = √2 4 = (2 4 ) 1/2 = 2 2 = 4
- √4 = √2 2 = (2 2 ) 1/2 = 2 1 = 2
Обратите внимание, что мы следовали последовательности 2 16 → 2 8 → 2 4 → 2 2 → 2 1 . На каждой итерации мы вдвое уменьшаем показатель степени двойки. Это интересно, потому что это связано с тем, что мы уже знаем - вы можете разделить число k только пополам O (log k) раз, прежде чем оно упадет до нуля.
Итак, возьмите любое число n и запишите его как n = 2 k . Каждый раз, когда вы извлекаете квадратный корень из n, вы уменьшаете показатель в этом уравнении вдвое. Следовательно, может быть применено только O (log k) квадратных корней до того, как k упадет до 1 или ниже (в этом случае n упадет до 2 или ниже). Поскольку n = 2 k , это означает, что k = log 2 n, и, следовательно, количество извлеченных квадратных корней равно O (log k) = O (log log n). Следовательно, если есть алгоритм, который работает, многократно сокращая проблему до подзадачи размера, который является квадратным корнем из исходного размера проблемы, этот алгоритм завершится после O (log log n) шагов.
Одним из реальных примеров этого является дерево Ван Эмде Боаса.(vEB-tree) структура данных. VEB-дерево - это специализированная структура данных для хранения целых чисел в диапазоне 0 ... N - 1. Оно работает следующим образом: корневой узел дерева имеет в себе √N указателей, разделяя диапазон 0 ... N - 1 в √N сегментов, каждая из которых содержит диапазон примерно из √N целых чисел. Затем каждая из этих корзин внутренне делится на √ (√ N) корзин, каждая из которых содержит примерно √ (√ N) элементов. Чтобы пройти по дереву, вы начинаете с корня, определяете, к какому сегменту вы принадлежите, а затем рекурсивно продолжаете в соответствующем поддереве. Из-за того, как структурировано vEB-дерево, вы можете определить за O (1) время, в какое поддерево спуститься, и поэтому после O (log log N) шагов вы достигнете нижней части дерева. Соответственно, поиск в vEB-дереве занимает только время O (журнал журнала N).
Другой пример - алгоритм ближайшей пары точек Хопкрофта-Фортуны . Этот алгоритм пытается найти две ближайшие точки в наборе 2D точек. Он работает, создавая сетку сегментов и распределяя точки по этим сегментам. Если в какой-либо точке алгоритма обнаруживается сегмент, содержащий более √N точек, алгоритм рекурсивно обрабатывает этот сегмент. Таким образом, максимальная глубина рекурсии составляет O (log log n), и с помощью анализа дерева рекурсии можно показать, что каждый слой в дереве выполняет O (n) работу. Следовательно, общее время выполнения алгоритма составляет O (n log log n).
O (log n) алгоритмы на малых входах
Есть несколько других алгоритмов, которые достигают времени выполнения O (log log n), используя такие алгоритмы, как двоичный поиск по объектам размера O (log n). Например, структура данных x-fast trie выполняет двоичный поиск по слоям дерева высотой O (журнал U), поэтому время выполнения для некоторых из его операций составляет O (журнал журнала U). Связанное y-быстрое дерево получает некоторые из своих периодов выполнения O (журнал журнала U), поддерживая сбалансированные BST из O (журнал U) узлов каждый, позволяя поиску в этих деревьях выполняться за время O (журнал журнала U). Дерево танго и родственные multisplay дерева структуры данных , в конечном итоге с O (журнал журнал п) в перспективе их анализа , поскольку они сохраняют деревья , которые содержат O (журнал п) элементов каждый.
Другие примеры
Другие алгоритмы достигают времени выполнения O (log log n) другими способами. Поиск с интерполяцией ожидал, что среда выполнения O (log log n) найдет число в отсортированном массиве, но анализ довольно сложен. В конечном итоге анализ работает, показывая, что количество итераций равно числу k, так что n 2 -k ≤ 2, для которого log log n является правильным решением. Некоторые алгоритмы, такие как алгоритм Черитона-Тарьяна MST , достигают времени выполнения, включающего O (log log n), путем решения сложной задачи оптимизации с ограничениями.
Надеюсь это поможет!
Один из способов увидеть фактор O (log log n) во временной сложности - это разделение, как описано в другом ответе, но есть другой способ увидеть этот фактор, когда мы хотим заключить сделку между временем и пространством / временем и приближение / время и твердость / ... алгоритмов, и у нас есть некоторая искусственная итерация в нашем алгоритме.
Например, SSSP (кратчайший путь из одного источника) имеет алгоритм O (n) на планарных графах, но до этого сложного алгоритма был гораздо более простой алгоритм (но все еще довольно сложный) со временем работы O (n log log n), Основа алгоритма следующая (просто очень приблизительное описание, и я бы предложил пропустить понимание этой части и прочитать другую часть ответа):
Но я хочу сказать, что здесь мы выбираем разделение размером O (log n / (log log n)). Если мы выберем другие подразделения, такие как O (log n / (log log n) ^ 2), которые могут работать быстрее и принесут другой результат. Я имею в виду, что во многих случаях (например, в алгоритмах аппроксимации или рандомизированных алгоритмах или алгоритмах, подобных SSSP, как указано выше), когда мы перебираем что-то (подзадачи, возможные решения, ...), мы выбираем номер итерации, соответствующий сделке этого у нас есть (время / пространство / сложность алгоритма / постоянный коэффициент алгоритма, ...). Так что, возможно, мы видим более сложные вещи, чем "log log n" в реальных рабочих алгоритмах.
источник