Оглавление
Повторяющийся логарифм
-
Определение повторяющегося логарифма
- Повторяющийся логарифм – это количество итераций логарифмирования для достижения значения меньше или равного 1.
- Используется для обозначения двоичного итерированного логарифма вместо натурального логарифма.
-
Математические свойства
- Определен для оснований, больших чем e^1/e, не только для 2 и e.
- Функция “суперлогарифмирования” slogb является обратной к операции тетрирования.
-
Применение в анализе алгоритмов
- Используется для анализа временной и пространственной сложности алгоритмов, таких как триангуляция Делоне и алгоритм Фюрера.
- Рост повторяющегося логарифма значительно медленнее, чем у самого логарифма или его повторений.
-
Связь с другими областями
- Тесно связан с обобщенной функцией логарифмирования в симметричной арифметике уровней-индексов.
- Аддитивная устойчивость числа равна O(log∗n).
- В теории сложности вычислений разница между DTIME и NTIME имеет порядок nlog∗n.
-
Дополнительные сведения
- Обратная функция Аккермана также имеет медленно растущую сложность.