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

Итерированный логарифм ${\displaystyle \log ^{*}n}$ в математике и информатике определяется как целочисленная функция, равная количеству итеративных логарифмирований аргумента, необходимых для того, чтобы результат стал меньше или равен 1. Эта функция определена для всех положительных чисел, но в приложениях аргумент, как правило, натуральное число. Более строго итерированный логарифм определяется рекурсивной формулой:

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

Итерированный логарифм определён для оснований ${\displaystyle b>e^{1/e}\approx 1{,}444667}$ A073229. Если положительное ${\displaystyle b<e^{1/e}}$, то определяющая его рекурсивная последовательность сходится к числу больше 1. В информатике обычно используют двоичный итерированный логарифм.

Эта функция возрастает неограниченно, но чрезвычайно медленно. Для всех мыслимых на практике аргументов её можно было бы заменить константой, но для формул, определённых на всей числовой оси, такая запись будет ошибочной. Значения двоичного итерированного логарифма для всех практически интересных аргументов не превосходят 5 и приведены ниже.

n	${\displaystyle \log _{2}^{*}n}$
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536 (~1019660)]	5

Применение

Итерированный логарифм возникает при анализе некоторых алгоритмов в оценках их вычислительной сложности^{[1][2][3][4][5]} Наиболее известна оценка временной сложности алгоритма Фюрера для умножения целых чисел — ${\displaystyle O(n\log n\cdot 2^{O(\log ^{*}n)})}$, и оценка для распределенного алгоритма 3-раскраски ${\displaystyle n}$-цикла в графе — ${\displaystyle O(\log ^{*}n)}$^[6]

Примечания

Эта страница в последний раз была отредактирована 31 августа 2023 в 23:11.