В компьютерной науке, в итерированного логарифм от, написанного журнала * (обычно читать « журнал звезда »), является количество раз логарифм функция должна быть итеративно применяется до результата меньше или равно. Простейшее формальное определение является результатом этого рекуррентного отношения :
Для положительных действительных чисел непрерывный суперлогарифм (обратная тетрация ) по существу эквивалентен:
т.е. повторный логарифм по основанию b равен, если n лежит в пределах интервала, где обозначает тетрацию. Однако для отрицательных действительных чисел логарифмическая звезда равна, а для положительных, поэтому две функции различаются для отрицательных аргументов.
Рисунок 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.
В информатике lg * часто используется для обозначения двоичного повторного логарифма, который повторяет двоичный логарифм (с основанием) вместо натурального логарифма (с основанием e).
Математически повторный логарифм хорошо определен для любого основания больше, чем, а не только для основания и основания e.
Повторный логарифм полезен при анализе алгоритмов и вычислительной сложности, появляясь во временных и пространственных границах сложности некоторых алгоритмов, таких как:
Повторный логарифм растет чрезвычайно медленно, намного медленнее, чем сам логарифм. Для всех значений n, относящихся к подсчету времени работы алгоритмов, реализованных на практике (т. Е. N ≤ 2 65536, что намного больше, чем предполагаемое количество атомов в известной вселенной), повторный логарифм с основанием 2 имеет значение no более 5.
Икс | lg * x |
---|---|
(−∞, 1] | 0 |
(1, 2] | 1 |
(2, 4] | 2 |
(4, 16] | 3 |
(16, 65536] | 4 |
(65536, 2 65536 ] | 5 |
Более высокие основания дают меньшие повторные логарифмы. Действительно, единственная функция, обычно используемая в теории сложности, которая растет медленнее, - это обратная функция Аккермана.
Повторный логарифм тесно связан с функцией обобщенного логарифма, используемой в симметричной арифметике индекса уровня. Он также пропорционален аддитивной стойкости числа, количеству раз, когда кто-то должен заменить число на сумму его цифр, прежде чем достигнет его цифрового корня.
В теории сложности вычислений Сантанам показывает, что вычислительные ресурсы DTIME - время вычислений для детерминированной машины Тьюринга - и NTIME - время вычислений для недетерминированной машины Тьюринга - различаются вплоть до