반복 로그

컴퓨터 과학에서, $n{\displaystyle }$ ${\displaystyle n$ writed logar* n ${\displaystyn}($$일반적$으로 "log star"로 읽음)의 반복 로그 함수가 1 ${\displaystyle 1}$보다 작거나 같기 전에 반복적으로 적용되어야 하는 횟수다$.$ 가장 간단한 공식 정의는 이러한 재발 관계의 결과물이다.

${\displaystyle \log ^{*n:={\base}0&{\\mbox{{n\leq 1;\\1+\log ^{*}(\logn)&{\mbox{{}}}}}}}$

양의 실수에서 연속 초 로그(역방향 테트라제이션)는 본질적으로 동일하다.

${\displaystyle \log ^{*n=\lceil \mathrm {slog} _{e}(n)\rceil }$

즉, 기지 b를 로그는 로그 ∗⁡ nxy{\displaystyle\log ^{*}n=y}만약 n에 놓여 있다. 이내에 간격 y − 1b<>n≤는 yb{\displaystyle ^{y-1}b<, n\leq)^{y}b}, yb)bb⋅ ⋅ b⏟는 y{\displaystyle{^{y}b}=\underbrace{b^{b^{\cdot ^{\cdot ^{b}}}}}_{y}}을 나타내te.trati단, 음수 실수의 경우 로그스타일은 0 ${\displaystyle 0$$\}$인 반면,${\displaystyle {}_{}}$ ${\displaystyle {\text{strong}}_{}}$ e${\displaystyle {}_{}}$(${\displaystyle }$- x${\displaystyle }$) ${\displaystyle \rceil }$=${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle \lceil {\text{lsloil}}}{e}(-x)\rceil$=-$1$$\}$인 경우에는$$ 두 기능이 음수 인수에 차이가 있다.

반복된 로그는 임의의 양의 실제 숫자를 수용하고 정수를 산출한다. 그래픽적으로는 그림 1에서 x축의${\displaystyle }$[${\displaystyle 0}$,${\displaystyle }$1$$ {\$displaystyle [0,1]$ 간격에 도달하기 위해 필요한 "zig-zags"의 수로 이해할 수 있다.

컴퓨터 과학에서 lg*는 종종 자연 로그(base e) 대신 이진 로그($base{\displaystyle \mathrm{}}$ 2$${\$displaystyle 2$를 반복하는 이진 반복 로그(binary eterated logarithm)를 나타내기 위해 사용된다.

수학적으로 반복된 로그는 $base{\displaystyle \mathrm{}}$ 2$$$${\$displaystyle 2}$ 및 base e에 대한 것뿐만 $아니라{\displaystyle {}^{}}$ e${\displaystyle {1\mathrm{}}^{}}$ / ${\displaystyle e^{}1}$1.${\displaystyle 44667}$ ${\displaystyle e^{1/e}\$약$1.4444667}$ 이상의 베이스에 대해 잘 정의되어 있다$.$

알고리즘 분석

반복 로그는 알고리즘 및 계산 복잡성의 분석에 유용하며, 다음과 같은 일부 알고리즘의 시간 및 공간 복잡성 한계에서 나타난다.

• 유클리드 최소 스패닝 트리: 무작위화된 O(n log*^[1]n) 시간을 알고 있는 점 집합의 델라나이 삼각 측량 찾기
• Fürer의 정수 곱셈 알고리즘: O(n log n 2^{O(lg* n)})
• 대략적인 최대값 찾기(최소한 중위수만큼 큰 요소): lg* n - 4 ~ lg* n + 2 병렬 작동.^[2]
• Richard Cole과 Uzi Vishkin의 3-coloring n-cycle: O(log* n) 동기식 통신 라운드에 대한 분산 알고리즘.^[3][4]
• 경로 압축을 사용한 가중 빠른 결합 ^[5]수행

반복된 로그는 로그 자체보다 훨씬 느린 속도로 성장한다. 실제로 구현된 알고리즘의 실행 시간 계산과 관련된 n의 모든 값에 대해(즉, 알려진 우주의 추정 원자 수보다 훨씬 많은 n ≤ 2⁶⁵⁵³⁶), 베이스 2를 가진 반복 로그는 5 이하의 값을 갖는다.

base-2 반복 로그

x	lg* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

베이스가 높을수록 반복 로그가 작아진다. 실제로 더 느리게 성장하는 복잡성 이론에서 흔히 사용되는 기능은 역아커만함수뿐이다.

기타 응용 프로그램

반복된 로그는 대칭 수준 지수 산술에 사용되는 일반화된 로그 함수와 밀접한 관련이 있다. 또한 디지털 루트에 도달하기 전에 숫자의 합으로 숫자를 교체해야 하는 횟수인 숫자의 첨가 지속성에 비례한다.

계산 복잡성 이론에서 산타남은^[6] 계산 리소스 DTIME(결정론적 튜링 시스템의 계산 시간)과 비결정론적 튜링 시스템의 계산 시간(NTIME)이 $최대{\displaystyle }$ n ${\displaystyle \sqrt{{\log }^{}}}$ ${\displaystyle \sqrt{{}^{}}}$ ${\displaystyle \sqrt{n}.}$ ${\displaystyle n{\sqrt {\log ^{*n}$까지 구별된다는 것을 보여준다.$}$

메모들

참조

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "3.2: Standard notations and common functions". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 55–56. ISBN 0-262-03293-7.