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

09.03.2021

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

log ∗ ⁡ n := { 0 if  n ⩽ 1 ; 1 + log ∗ ⁡ ( log ⁡ n ) if  n > 1 {displaystyle log ^{*}n:={egin{cases}0&{mbox{if }}nleqslant 1;1+log ^{*}(log n)&{mbox{if }}n>1end{cases}}}

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

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

Применение

Итерированный логарифм возникает при анализе некоторых алгоритмов в оценках их вычислительной сложности Наиболее известна оценка временной сложности алгоритма Фюрера для умножения целых чисел — O ( n log ⁡ n ⋅ 2 O ( log ∗ ⁡ n ) ) {displaystyle O(nlog ncdot 2^{O(log ^{*}n)})} , и оценка для алгоритма 3-раскраски n {displaystyle n} -цикла в графе — O ( log ∗ ⁡ n ) {displaystyle O(log ^{*}n)}