반복 로그

컴퓨터 과학에서, n의 반복 로그(영어: iterated logarithm)는 log* n (보통 "로그-스타"(log star)이라고 읽는다)로 쓰며, 로그 함수를 반복적으로 적용시켜서 결과 값이 1보다 같거나 작아질 때까지 걸리는 횟수이다. 가장 간단한 정식 정의는 이 점화식의 결과이다.

$\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}$

양수에서, 연속적인 초-로그 (테트레이션의 역함수)는 본질적으로 동일하다.

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

하지만 음수에서는 로그-스타는 0이고 양의 x에 대해서 $\lceil {\text{slog}}_{e}(-x)\rceil =-1$이므로 두 함수는 음수에서는 다르다.

그림 1. ln* 4 = 2임을 보여주고 있다

계산 과학에서, lg*는 종종 이진 로그를 반복하는 이진 반복 로그를 나타낼 때 쓰인다. 반복 로그는 어떤 양의 실수를 받아서 정수를 얻는다. 그래픽에서 보면, 이 함수는 그림 1에서 x축의 구간 [0, 1]에 도달하기까지 필요한 지그재그의 숫자로 생각할 수 있다.

수학적으로는 반복 로그는 밑이 2이거나 e일 때만 잘 정의되어 있는 것이 아니라 $1$보다 큰 어떤 밑에 대해서 모두 잘 정의되어 있다.

알고리즘 분석

반복 로그는 알고리즘 분석과 계산 복잡도에서 다음과 같은 일부 알고리즘의 시간과 공간 복잡도에서 나타난다.

• 유클리드 최소 신장 트리를 아는 점들의 집합에서 델로네 삼각분할을 찾기: 무작위적O(n log* n) 시간
• 정수 곱셈에서의 퓨러 알고리즘: O(n log n 2^O(lg* n))
• 추정 최댓값을 찾기(적어도 중앙값보다 큰 원소): lg* n − 4 to lg* n + 2 병렬 연산
• 리차드 콜(Richard Cole)과 우지 비슈킨(Uzi Vishkin)의 n-순환 그래프의 3색 색칠에 대한 분산 알고리즘: O(log* n) 동기 통신 라운드.
• 경로 압축을 한 weighted quick-union

반복 로그는 로그보다도 더 느리게 증가한다. 실제로 수행한 알고리즘의 실행시간의 계에 관련된 모든 n값에 대해서(즉, n ≤ 2⁶⁵⁵³⁶으로 2⁶⁵⁵³⁶은 알려진 우주의 원자의 개수의 추정치보다 훨씬 크다), 밑이 2인 반복 로그는 5보다 큰 값을 가지지 않는다.

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

밑이 더 크면 반복 로그의 횟수가 줄어든다. 당연히도, 복잡도 이론에서 일반적으로 사용하는 더 느리게 증가하는 유일한 함수는 역 아커만 함수이다.

다른 적용

반복 로그는 symmetric level-index arithmetic에서 쓰이는 generalized logarithm function과 밀접하게 관련되어 있다. 또한, 어떤 숫자를 그 숫자의 각 자릿수를 더한 값으로 바꿔써서 자릿수근에 도달하기까지 걸리는 횟수인 덧셈 지속성에 비례한다.

산다남은 DTIME과 NTIME은 $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》 2판. MIT Press and McGraw-Hill. 55–56쪽. ISBN 0-262-03293-7.