Итерированный логарифм

В компьютерной науке , в итерированного логарифм от , написанного журнала * (обычно читать « журнал звезда »), является количество раз логарифм функция должна быть итеративно применяется до результата меньше или равно . Простейшее формальное определение является результатом этого рекуррентного отношения : ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 1}$

\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}

Для положительных действительных чисел непрерывный суперлогарифм (обратная тетрация ) по существу эквивалентен:

\log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil

т.е. повторный логарифм по основанию b равен, если n лежит в пределах интервала , где обозначает тетрацию. Однако для отрицательных действительных чисел логарифмическая звезда равна , а для положительных , поэтому две функции различаются для отрицательных аргументов. $\log ^{*}n=y$ $^{y-1}b<n\leq \ ^{y}b$ ${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}$ $0$ $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ $x$

Рисунок 1. Демонстрация log * 4 = 2 для повторного логарифма по основанию e. Значение повторного логарифма можно найти "зигзагом" на кривой y = log _b (x) от входа n до интервала [0,1]. В этом случае b = e. Зигзаг влечет за собой начало с точки (n, 0) и итеративное перемещение к (n, log _b (n)), к (0, log _b (n)), к (log _b (n), 0).

Повторный логарифм принимает любое положительное действительное число и дает целое число . Графически это можно понять как количество «зигзагов», необходимое на рисунке 1 для достижения интервала по оси x . $[0,1]$

В информатике lg * часто используется для обозначения двоичного повторного логарифма , который повторяет двоичный логарифм (с основанием ) вместо натурального логарифма (с основанием e ). $2$

Математически повторный логарифм хорошо определен для любого основания больше, чем , а не только для основания и основания e . $e^{1/e}\approx 1.444667$ $2$

Анализ алгоритмов [ править ]

Повторный логарифм полезен при анализе алгоритмов и вычислительной сложности , появляясь во временных и пространственных границах сложности некоторых алгоритмов, таких как:

Нахождение триангуляции Делоне набора точек, зная евклидово минимальное остовное дерево : рандомизированное время O ( n log * n ). ^[1]
Алгоритм Фюрера для целочисленного умножения: O ( n log n 2 ^{O (lg * n )} ).
Нахождение приблизительного максимума (размер элемента не меньше медианы): от lg * n - 4 до lg * n + 2 параллельных операции. ^[2]
Ричард Коул и Узи Вишкин «ы распределены алгоритм для 3-раскраски в п - цикл : O ( журнал * п ) синхронных раундов связи. ^[3]^[4]
Выполнение взвешенного быстрого объединения со сжатием пути. ^[5]

Повторный логарифм растет чрезвычайно медленно, намного медленнее, чем сам логарифм. Для всех значений n, относящихся к подсчету времени работы алгоритмов, реализованных на практике (т. Е. N ≤ 2 ⁶⁵⁵³⁶ , что намного больше, чем предполагаемое количество атомов в известной вселенной), повторный логарифм с основанием 2 имеет значение no более 5.

Повторный логарифм по основанию 2
Икс	lg * x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536)	4
(65536, 2 ⁶⁵⁵³⁶ ]	5

Более высокие основания дают меньшие повторные логарифмы. Действительно, единственная функция, обычно используемая в теории сложности, которая растет медленнее, - это обратная функция Аккермана .

Другие приложения [ править ]

Повторный логарифм тесно связан с функцией обобщенного логарифма, используемой в симметричной арифметике индекса уровня . Он также пропорционален аддитивной стойкости числа , количеству раз, когда кто-то должен заменить число на сумму его цифр, прежде чем достигнет его цифрового корня .

В теории вычислительной сложности Сантанам ^[6] показывает, что вычислительные ресурсы DTIME - время вычислений для детерминированной машины Тьюринга - и NTIME - время вычислений для недетерминированной машины Тьюринга - различаются вплоть до $n{\sqrt {\log ^{*}n}}.$

Заметки [ править ]

^ Оливье Девиллерс, «Рандомизация дает простые O (n log * n) алгоритмы для сложных ω (n) задач». Международный журнал вычислительной геометрии и приложений 2 : 01 (1992), стр. 97–111.
↑ Нога Алон и Йоси Азар, «Поиск приблизительного максимума». SIAM Journal on Computing 18 : 2 (1989), стр. 258–267.
^ Ричард Коул и Узи Вишкин: «Детерминированное подбрасывание монеты с приложениями к оптимальному ранжированию в параллельном списке», Информация и управление 70: 1 (1986), стр. 32–53.
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8. Раздел 30.5.
^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
^ О разделителях, сегрегаторах и времени против пространства

Ссылки [ править ]

Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «3.2: Стандартные обозначения и общие функции». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 55–56. ISBN 0-262-03293-7.

[1] Оливье Девиллерс, «Рандомизация дает простые O (n log * n) алгоритмы для сложных ω (n) задач». Международный журнал вычислительной геометрии и приложений 2 : 01 (1992), стр. 97–111.

[2] Нога Алон и Йоси Азар, «Поиск приблизительного максимума». SIAM Journal on Computing 18 : 2 (1989), стр. 258–267.

[3] Ричард Коул и Узи Вишкин: «Детерминированное подбрасывание монеты с приложениями к оптимальному ранжированию в параллельном списке», Информация и управление 70: 1 (1986), стр. 32–53.

[4] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8. Раздел 30.5.

[5] ttps://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

[6] О разделителях, сегрегаторах и времени против пространства

[1]