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

редактировать
Чтобы узнать о теореме теории вероятностей, см. Закон повторного логарифма.

В компьютерной науке, в итерированного логарифм от, написанного журнала * (обычно читать « журнал звезда »), является количество раз логарифм функция должна быть итеративно применяется до результата меньше или равно. Простейшее формальное определение является результатом этого рекуррентного отношения : п {\ displaystyle n}   п {\ displaystyle n} 1 {\ displaystyle 1}

бревно * п знак равно { 0 если  п 1 ; 1 + бревно * ( бревно п ) если  п gt; 1 {\ displaystyle \ log ^ {*} n: = {\ begin {cases} 0 amp; {\ t_dv {if}} n \ leq 1; \\ 1+ \ log ^ {*} (\ log n) amp; {\ t_dv {if}} ngt; 1 \ end {case}}}

Для положительных действительных чисел непрерывный суперлогарифм (обратная тетрация ) по существу эквивалентен:

бревно * п знак равно s л о грамм е ( п ) {\ Displaystyle \ log ^ {*} п = \ lceil \ mathrm {slog} _ {e} (n) \ rceil}

т.е. повторный логарифм по основанию b равен, если n лежит в пределах интервала, где обозначает тетрацию. Однако для отрицательных действительных чисел логарифмическая звезда равна, а для положительных, поэтому две функции различаются для отрицательных аргументов. бревно * п знак равно у {\ Displaystyle \ log ^ {*} п = у} у - 1 б lt; п   у б {\ Displaystyle ^ {Y-1} б lt;п \ Leq \ ^ {у} б} у б знак равно б б б у {\ displaystyle {^ {y} b} = \ underbrace {b ^ {b ^ {\ cdot ^ {\ cdot ^ {b}}}}} _ {y}} 0 {\ displaystyle 0} тяжелая работа е ( - Икс ) знак равно - 1 {\ displaystyle \ lceil {\ text {slog}} _ {e} (- x) \ rceil = -1} Икс {\ displaystyle x}

Рисунок 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. [ 0 , 1 ] {\ displaystyle [0,1]}

В информатике lg * часто используется для обозначения двоичного повторного логарифма, который повторяет двоичный логарифм (с основанием) вместо натурального логарифма (с основанием e). 2 {\ displaystyle 2}

Математически повторный логарифм хорошо определен для любого основания больше, чем, а не только для основания и основания e. е 1 / е 1.444667 {\ displaystyle e ^ {1 / e} \ приблизительно 1.444667} 2 {\ displaystyle 2}

СОДЕРЖАНИЕ

  • 1 Анализ алгоритмов
  • 2 Другие приложения
  • 3 Примечания
  • 4 ссылки

Анализ алгоритмов

Повторный логарифм полезен при анализе алгоритмов и вычислительной сложности, появляясь во временных и пространственных границах сложности некоторых алгоритмов, таких как:

Повторный логарифм растет чрезвычайно медленно, намного медленнее, чем сам логарифм. Для всех значений n, относящихся к подсчету времени работы алгоритмов, реализованных на практике (т.  Е. N ≤ 2 65536, что намного больше, чем предполагаемое количество атомов в известной вселенной), повторный логарифм с основанием 2 имеет значение no более 5.

Повторный логарифм по основанию 2
Икс lg *  x
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 2 65536 ] 5

Более высокие основания дают меньшие повторные логарифмы. Действительно, единственная функция, обычно используемая в теории сложности, которая растет медленнее, - это обратная функция Аккермана.

Другие приложения

Повторный логарифм тесно связан с функцией обобщенного логарифма, используемой в симметричной арифметике индекса уровня. Он также пропорционален аддитивной стойкости числа, количеству раз, когда кто-то должен заменить число на сумму его цифр, прежде чем достигнет его цифрового корня.

В теории сложности вычислений Сантанам показывает, что вычислительные ресурсы DTIME - время вычислений для детерминированной машины Тьюринга - и NTIME - время вычислений для недетерминированной машины Тьюринга - различаются вплоть до п бревно * п . {\ displaystyle n {\ sqrt {\ log ^ {*} n}}.}

Примечания

использованная литература

Последняя правка сделана 2023-04-04 04:02:21
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте