Что может привести к сложности алгоритма O (log log n)?

Ответ 1

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
• 8,192/2 = 4,096
• 4,096/2 = 2,048
• 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 шагов, а также тот случай, когда 65536 = 2 ¹⁶.

Но, если мы возьмем квадратный корень на каждом уровне, получим

• & radic; 65536 = 256
• & radic; 256 = 16
• & radic; 16 = 4
• & radic; 4 = 2

Обратите внимание, что для достижения всего пути до 2 требуется всего четыре шага. Почему это? Ну, пусть переписать эту последовательность в терминах степеней двух:

• & radic; 65,536 = & radic; 2 ¹⁶= (2 ¹⁶) ^1/2= 2 ⁸= 256
• & radic; 256 = & radic; 2 ⁸= (2 ⁸) ^1/2= 2 ⁴= 16
• & radic; 16 = & radic; 2 ⁴= (2 ⁴) ^1/2= 2 ²= 4
• & radic; 4 = & radic; 2 ²= (2 ²) ^1/2= 2 ¹= 2

Обратите внимание, что мы следовали последовательности 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹. На каждой итерации мы сокращаем показатель степени два пополам. Это интересно, потому что это связано с тем, что мы уже знаем - вы можете только разделить число k пополам O (log k) раз до того, как оно упадет до нуля.

Итак, возьмем любое число n и запишем его как n = 2 ^k. Каждый раз, когда вы берете квадратный корень из n, вы уменьшаете экспоненту в этом уравнении. Следовательно, могут быть только O (log k) квадратные корни, примененные до того, как k капель до 1 или ниже (в этом случае n падает до 2 или ниже). Так как n = 2 ^k это означает, что k = log ₂ n, и поэтому число взятых квадратных корней равно O (log k) = O (log log n), Поэтому, если есть алгоритм, который работает путем многократного уменьшения проблемы до подзадачи размера, которая является квадратным корнем из исходного размера проблемы, этот алгоритм завершится после шагов O (log log n).

Одним из реальных примеров этого является структура данных van Emde Boas tree (vEB-tree). Дерево vEB является специализированной структурой данных для хранения целых чисел в диапазоне 0... N - 1. Оно работает следующим образом: корень node дерева имеет & radic; N указателей в нем, разделяя диапазон 0.. N - 1 в & radic; N ведер, каждый из которых содержит диапазон грубо-радикальных N целых чисел. Затем эти ведра внутренне подразделяются на & radic; (& radic; N) ведра, каждый из которых содержит грубо и радиус (& radic; N) элементов. Чтобы пересечь дерево, вы начинаете с корня, определяете, к какому ведеру вы принадлежите, а затем рекурсивно продолжаете в соответствующем поддереве. Из-за того, как структурировано дерево vEB, вы можете определить в O (1) время, из которого поддерево спускаться, и поэтому после шагов O (log log N) вы достигнете дна дерева. Соответственно, поиск в дереве vEB занимает только время O (log log N).

Другим примером является алгоритм ближайшей пары точек Hopcroft-Fortune, Этот алгоритм пытается найти две ближайшие точки в наборе двумерных точек. Он работает, создавая сетку ведер и распределяя точки в эти ведра. Если в какой-либо точке алгоритма найден ковш, который имеет больше, чем & radic; 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 (log U), поэтому среда выполнения для некоторых из его операций O (log log U). Связанный с этим y-fast trie получает некоторые из его времени выполнения O (log log U), поддерживая сбалансированные BST-адреса узлов O (log U) каждый, что позволяет поиск в этих деревьях для запуска во времени O (log log U). дерево танго и связанные с ним многослойные деревья структуры данных O (log log n) в своих анализах, потому что они поддерживают деревья, которые содержат элементы O (log n) каждый.

Другие примеры

Другие алгоритмы достигают времени выполнения O (log log n) другими способами. Интерполяционный поиск ожидал, что во время выполнения O (log log n) найдет номер в отсортированном массиве, но анализ довольно востребован. В конечном итоге анализ работает, показывая, что число итераций равно числу k, для которого n ^{2 -k} & le; 2, для которого log log n является правильным решением. Некоторые алгоритмы, такие как алгоритм MST Cheriton-Tarjan, приходят во время выполнения с использованием O (log log n) путем решения сложной задачи с ограниченной оптимизацией.

Надеюсь, это поможет!

Ответ 2

Один из способов увидеть коэффициент O (log log n) во временной сложности - это деление, как описано в другом ответе, но есть еще один способ увидеть этот фактор, когда мы хотим совершить сделку между временем и пространство/время и аппроксимация/время и твердость /... алгоритмов, и у нас есть некоторая искусственная итерация по нашему алгоритму.

Например, SSSP (кратчайший путь с одним источником) имеет алгоритм O (n) на плоских графах, но до этого сложного алгоритма был намного более простой алгоритм (но довольно жесткий) с временем выполнения O (n log log n), база алгоритма следующая (просто очень грубое описание, и я бы предложил пропустить понимание этой части и прочитать другую часть ответа):

• разделите граф на части размера O (log n/(log log n)) с некоторым ограничением.
• Предположим, что каждая из упомянутых частей node в новом графе G 'затем вычислит SSSP для G' за время O (| G '| * log | G' |) == > здесь, потому что | G '| = O (| G | * log log n/log n), мы можем видеть фактор (log log n).
• Вычислить SSSP для каждой части: снова, потому что у нас есть O (| G '|) часть, и мы можем вычислить SSSP для всех частей во времени | n/logn | * | log n/log logn * log (logn/log log n).
• весовые коэффициенты обновления, эта часть может быть выполнена в O (n). для более подробной информации эта лекция хороша.

Но я хочу сказать, что мы выбираем деление на размер O (log n/(log log n)). Если мы выберем другие деления, такие как O (log n/(log log n) ^ 2), который может работать быстрее и приносит другой результат. Я имею в виду, во многих случаях (например, в алгоритмах аппроксимации или рандомизированных алгоритмах или таких алгоритмах, как SSSP, как указано выше), когда мы перебираем что-то (подзадачи, возможные решения,...), мы выбираем число итераций, соответствующее торговле этого мы имеем (время/пространство/сложность алгоритма/постоянный множитель алгоритма,...). Возможно, мы видим более сложные вещи, чем "log log n" в реальных рабочих алгоритмах.