반복 로그

1. 개요

반복 로그는 주어진 수에 로그 함수를 반복적으로 적용하여 결과가 1 이하가 될 때까지의 반복 횟수를 의미한다. $\backslash log^*\; n$으로 표기하며, 재귀적 또는 반복적으로 정의할 수 있다. 컴퓨터 과학에서는 이진 로그를 반복하는 $\backslash lg^*n$을 사용하기도 한다. 반복 로그는 알고리즘 분석 및 계산 복잡도 이론에서 일부 알고리즘의 시간 및 공간 복잡도를 나타내는 데 사용되며, 로그 함수보다 훨씬 느리게 증가한다.

2. 정의

반복 로그는 주어진 수에 대해 로그 함수를 반복적으로 적용하여 그 결과가 1 이하가 될 때까지의 반복 횟수를 의미한다. $n$에 대한 반복 로그는 $\backslash log^*\; n$ (로그 스타 $n$)으로 표기한다.

반복 로그는 실수 전체에서 정의되며, 음이 아닌 정수를 값으로 갖는다. 양의 실수에 대해서는, $xy$ 평면에서 $x$축 위의 구간 $(0,\; 1]$에 도달하기 위해 필요한 지그재그의 수로 도식적으로 이해할 수 있다.

컴퓨터 과학에서는 자연 로그 대신 이진 로그를 반복하는 반복 로그 $\backslash lg^*n\; :=\; \backslash log^*\_2n$도 사용되고 있다. 수학적으로는, $e$나 $2$ 뿐만 아니라, $e^\{1/e\}\; \backslash approx\; 1.444667$보다 큰 임의의 밑에 대해 잘 정의된다.

2.1. 재귀적 정의

반복 로그는 $\backslash log^*\; n$(로그 스타 $n$)으로 표기되며, 다음과 같이 재귀적으로 정의된다.

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


함수의 반복을 사용하면 다음과 같이 정의할 수도 있다.

:$\backslash log^*\; n\; :=\; \backslash min\backslash left\backslash \{i\; \backslash geq\; 0\; :\; \backslash log^\{(i)\}n\; \backslash leq\; 1\; \backslash right\backslash \}$

양의 실수에서는 연속성의 초대수와 같다.

:$\backslash log^*\; n\; =\; \backslash lceil\; \backslash mathrm\{slog\}\backslash ,n\; \backslash rceil$

다시 말해, $b$를 반복 로그의 밑으로 하여, $n$이 구간 $(^\{y-1\}b,\backslash ,^\{y\}b]$에 있을 때, 그 반복 로그는 $\backslash log^*\_b\; n\; =\; y$로 표시된다. 여기서 $\{^\{y\}b\}\; =\; \backslash underbrace\{b^\{b^\{\backslash cdot^\{\backslash cdot^\{b\}\}\}\}\}\_y$는 테트레이션이다. 단, 음의 실수 $x$에 대해 반복 로그의 값은 $\backslash log^*\; x\; =\; 0$이지만, $\backslash lceil\; \backslash mathrm\{slog\}\backslash ,x\; \backslash rceil\; =\; -1$이므로, 음의 실수에서는 앞서 제시한 관계는 성립하지 않게 된다.

반복 로그는 실수 전체에서 정의되며, 음이 아닌 정수를 값역으로 갖는다. 양의 실수에 대해서는, $xy$ 평면에서 $x$축 위의 구간 $(0,\; 1]$에 도달하기 위해 필요한 지그재그의 수로 도식적으로 이해할 수 있다.

컴퓨터 과학에서는 자연 로그 대신 이진 로그를 반복하는 반복 로그 $\backslash lg^*n\; :=\; \backslash log^*\_2n$도 사용되고 있다. 수학적으로는, $e$나 $2$ 뿐만 아니라, $e^\{1/e\}\; \backslash approx\; 1.444667$보다 큰 임의의 밑에 대해 잘 정의된다.

2.2. 반복적 정의

함수의 반복을 사용하여 다음과 같이 정의할 수도 있다.

:$\backslash log^*\; n\; :=\; \backslash min\backslash left\backslash \{i\; \backslash geq\; 0\; :\; \backslash log^\{(i)\}n\; \backslash leq\; 1\; \backslash right\backslash \}$

2.3. 초대수와의 관계

양의 실수에서 반복 로그는 연속 초대수(super-logarithm)의 천장 함수와 같다. 즉, $b$를 반복 로그의 밑으로 할 때, $n$이 구간 $(^\{y-1\}b,\backslash ,^\{y\}b]$에 있으면, 반복 로그는 $\backslash log^*\_b\; n\; =\; y$로 표시된다. 여기서 $\{^\{y\}b\}\; =\; \backslash underbrace\{b^\{b^\{\backslash cdot^\{\backslash cdot^\{b\}\}\}\}\}\_y$는 테트레이션이다. 단, 음의 실수 $x$에 대해 반복 로그의 값은 $\backslash log^*\; x\; =\; 0$이지만, $\backslash lceil\; \backslash mathrm\{slog\}\backslash ,x\; \backslash rceil\; =\; -1$이므로, 음의 실수에서는 앞서 제시한 관계가 성립하지 않는다.

3. 알고리즘 분석

반복 로그는 알고리즘 분석과 계산 복잡도 이론에서 일부 알고리즘의 시간 및 공간 복잡도를 나타내는 데 사용된다. 반복 로그는 로그 함수보다 훨씬 느리게 증가하며, 복잡도 이론에서 이보다 더 느리게 증가하는 유일한 함수는 역 아커만 함수이다.

3.1. 예시

반복 로그는 알고리즘 분석과 계산 복잡도 이론에서 일부 알고리즘의 시간 및 공간 복잡도를 나타내는 데 사용된다. 다음은 그 예시이다.

* 유클리드 최소 신장 트리가 알려진 점 집합에 대한 델로네 삼각분할 찾기: 무작위적 O(n log* n) 시간
* 정수 곱셈에서의 퓨러 알고리즘: O(n log n 2^{O(log* n)})
* 근사 최댓값 (중앙값 이상인 요소) 찾기: log* n − 1 ± 3 병렬 연산
* 리차드 콜과 우지 비슈킨의 n-순환 그래프의 3색 색칠에 대한 분산 알고리즘: O(log* n) 동기 통신 라운드.
* 경로 압축을 사용한 가중 유니온-파인드(weighted quick-union) 알고리즘

실제로 다루는 모든 n 값(n ≤ 2⁶⁵⁵³⁶, 이는 알려진 우주의 원자 수 추정치보다 훨씬 크다)에 대해, 밑이 2인 반복 로그는 5 이하의 값을 가진다.

3.2. 성장 속도

반복 로그는 로그 함수보다 훨씬 느리게 증가한다. 실제로 사용되는 범위 내에서(n ≤ 2⁶⁵⁵³⁶), 밑이 2인 반복 로그 값은 5를 넘지 않는다. 여기서 2⁶⁵⁵³⁶은 알려진 우주의 원자 개수의 추정치보다 훨씬 큰 값이다.

4. 기타 응용

반복 로그는 대칭 수준 지수 산술에서 사용되는 일반화된 로그 함수와 밀접하게 관련되어 있다. 숫자의 덧셈 지속성(어떤 수가 디지털 루트에 도달하기까지 숫자를 자릿수의 합으로 바꿔야 하는 횟수)은 $O(\backslash log^*\; n)$이다.

5. 계산 복잡도 이론

계산 복잡도 이론에서 산타남은 DTIME (결정적 튜링 기계의 계산 자원)과 NTIME (비결정적 튜링 기계의 계산 시간)이 $n\backslash sqrt\{\backslash log^*n\}$까지 다를 수 있음을 보였다.