Есть ли алгоритм с временной сложностью O(lg * n) (функция повторного логарифма)?
В информатике повторный логарифм числа n, записываемый как log* n (обычно читаемый как "log star"), представляет собой число раз, которое функция логарифма должна быть применена итеративно, прежде чем результат станет меньше или равен 1. Самое простое формальное определение является результатом этой рекурсивной функции:
Есть ли алгоритм с временной сложностью O(LG * N)?
1 ответ
Если вы реализуете алгоритм поиска объединения со сжатием пути и объединением по рангу, объединение и поиск будут иметь сложность O(log*(n)),
Редко, но не неслыханно, чтобы log* n появлялся при анализе алгоритмов во время выполнения. Вот несколько случаев, когда появляется log* n.
Подход 1: сокращение с помощью лог-фактора
Многие алгоритмы "разделяй и властвуй" работают, преобразуя входные данные размера n во входные данные размера n / k. Количество фаз этих алгоритмов тогда равно O(logn), поскольку вы можете разделить только на константу O(logn) раз, прежде чем уменьшите ввод до постоянного размера. В этом смысле, когда вы видите, что "входные данные делятся на константу", вы должны подумать: "так что их можно разделить только O(logn) раз, прежде чем у нас закончатся вещи для деления".
В более редких случаях некоторые алгоритмы работают за счет уменьшения размера входных данных на логарифмический коэффициент. Например, одна структура данных для задачи запроса полугруппы диапазонов работает, разбивая более крупную задачу на блоки размером log n, а затем рекурсивно разделяя каждый блок размера log n на блоки размера log log n и т. Д. Этот процесс в конечном итоге останавливается один раз блоки достигают некоторого небольшого постоянного размера, что означает, что он останавливается после O(log* n) итераций. (Этот конкретный подход затем может быть улучшен, чтобы дать структуру данных, в которой блоки имеют размер log* n для общего числа раундов O(log** n), в конечном итоге сходимость к оптимальной структуре со временем выполнения O(α(n)), где α (n) - обратная функция Аккермана.
Подход 2: сжатие цифр чисел
В приведенном выше разделе рассказывается о подходах, которые явно разбивают большую проблему на более мелкие части, размеры которых логарифмичны по отношению к размеру исходной задачи. Однако есть другой способ взять ввод размера n и уменьшить его до ввода размера O(logn): заменить ввод чем-то, примерно сопоставимым по размеру с его количеством цифр. Поскольку для записи числа n требуется O(logn) цифр для записи, это приводит к уменьшению размера числа на величину, необходимую для возникновения члена O(log* n).
В качестве простого примера рассмотрим алгоритм вычисления цифрового корня числа. Это число, которое вы получаете, многократно складывая цифры числа, пока не уменьшите их до одной цифры. Например, цифровой корень 78979871 можно найти, вычислив
7 + 8 + 9 + 7 + 9 + 8 + 7 + 1 = 56
5 + 6 = 11
1 + 1 = 2
2
и получение цифрового рута из двух. Каждый раз, когда мы суммируем цифры числа, мы заменяем число n числом, которое не превышает 9 ⌈log10 n⌉, поэтому количество раундов равно O(log* n). (При этом общее время выполнения равно O(logn), поскольку мы должны учитывать работу, связанную с сложением цифр числа, а добавление цифр исходного числа доминирует во времени выполнения.)
В качестве более сложного примера есть параллельный алгоритм для трехкратной раскраски узлов дерева, описанный в статье "Нарушение параллельной симметрии в разреженных графах" Голдберга и др. Алгоритм работает путем многократной замены чисел более простыми числами, образованными суммированием определенных битов чисел, а необходимое количество раундов, как и в упомянутом выше подходе, равно O(log* n).
Надеюсь это поможет!