Итерированный логарифм в математике и информатике определяется как целочисленная функция, равная количеству итеративных логарифмирований аргумента, необходимых для того, чтобы результат стал меньше или равен 1. Эта функция определена для всех положительных чисел, но в приложениях аргумент, как правило, натуральное число. Более строго итерированный логарифм определяется рекурсивной формулой:
Итерированный логарифм определён для оснований . Если положительное , то определяющая его рекурсивная последовательность сходится к числу больше 1. В информатике обычно используют двоичный итерированный логарифм.
Эта функция возрастает неограниченно, но чрезвычайно медленно. Для всех мыслимых на практике аргументов её можно было бы заменить константой, но для формул, определённых на всей числовой оси, такая запись будет ошибочной. Значения двоичного итерированного логарифма для всех практически интересных аргументов не превосходят 5 и приведены ниже.
n (−∞, 1] 0 (1, 2] 1 (2, 4] 2 (4, 16] 3 (16, 65536] 4 (65536, 265536 (~1019729)] 5
Применение Итерированный логарифм возникает при анализе некоторых алгоритмов в оценках их вычислительной сложностиOlivier Devillers, «Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.». International Journal of Computational Geometry & Applications 2:01 (1992), pp. 971—11.Noga Alon and Yossi Azar, «Finding an Approximate Maximum». SIAM Journal of Computing 18:2 (1989), pp. 2582—67. Наиболее известна оценка временной сложности алгоритма Фюрера для умножения целых чисел — , и оценка для распределенного алгоритма 3-раскраски -цикла в графе — Richard Cole and Uzi Vishkin: «Deterministic coin tossing with applications to optimal parallel list ranking», Information and Control 70:1(1986), pp. 325—3.
Примечания
Категория:Теория сложности вычислений Категория:Логарифмы