반복 로그

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 알고리즘 분석
- 3.1. 예시
- 3.2. 성장 속도
4. 기타 응용
5. 계산 복잡도 이론
참조

1. 개요

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

더 읽어볼만한 페이지

점근 해석 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.
점근 해석 - 섭동 이론
섭동 이론은 정확히 풀리는 문제에 작은 변화가 있을 때 급수로 표현하여 근사해를 구하는 방법으로, 초기 해에 보정항을 더하는 방식으로 고전역학, 양자역학 등 다양한 분야에서 활용되며 섭동 형태와 적용 차수에 따라 구분된다.
로그 - 상용로그
상용로그는 10을 밑으로 하는 로그로, 십진법에 기반하여 log x 또는 lg x로 표기되며, 지표를 통해 진수의 자릿수 파악이 용이하여 과학적 측정에 활용되고 헨리 브리그스의 공로로 '브리그스의 로그'라고도 불린다.
로그 - 자연로그
자연로그는 밑이 e인 로그 함수로, ln(x) 등으로 표기되며 직교쌍곡선 아래 면적으로 정의되거나 지수 함수의 역함수로 정의될 수 있고, 다양한 수학적 성질과 함께 여러 분야에서 활용되며 복소 로그 함수로 확장되기도 한다.

반복 로그
개요
정의	급증의 역함수
함수 종류	수학 함수, 컴퓨터 과학 함수
수학적 정의
정의	반복 로그 함수는 밑이 b인 로그 함수를 적용해야 x가 1보다 작거나 같아지는 횟수이다.
표기	log* x 또는 log* (x)
수식	log* x := 0 (x ≤ 1) log* x := 1 + log* (log x) (x > 1)
예시	log* (2) ≈ 1.44, log* (4) ≈ 2.44, log* (16) ≈ 3.44
컴퓨터 과학에서의 활용
시간 복잡도 분석	알고리즘의 시간 복잡도를 분석하는 데 유용하게 사용된다.
예시	최소 스패닝 트리 알고리즘, 병합 정렬
관련 함수
아커만 함수	매우 빠르게 증가하는 함수이며, 반복 로그 함수와 밀접한 관련이 있다.
지수 함수	반복 로그 함수의 역함수이다.

2. 정의

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

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

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

2. 1. 재귀적 정의

반복 로그는

\log^* n

(로그 스타

n

)으로 표기되며, 다음과 같이 재귀적으로 정의된다.

:

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

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

:

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

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

:

\log^* n = \lceil \mathrm{slog}\,n \rceil

다시 말해,

b

를 반복 로그의 밑으로 하여,

n

이 구간

(^{y-1}b,\,^{y}b]

에 있을 때, 그 반복 로그는

\log^*_b n = y

로 표시된다. 여기서

{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y

는 테트레이션이다. 단, 음의 실수

x

에 대해 반복 로그의 값은

\log^* x = 0

이지만,

\lceil \mathrm{slog}\,x \rceil = -1

이므로, 음의 실수에서는 앞서 제시한 관계는 성립하지 않게 된다.

반복 로그는 실수 전체에서 정의되며, 음이 아닌 정수를 값역으로 갖는다. 양의 실수에 대해서는,

xy

평면에서

x

축 위의 구간

(0, 1]

에 도달하기 위해 필요한 지그재그의 수로 도식적으로 이해할 수 있다.

컴퓨터 과학에서는 자연 로그 대신 이진 로그를 반복하는 반복 로그

\lg^*n := \log^*_2n

도 사용되고 있다. 수학적으로는,

e

나

2

뿐만 아니라,

e^{1/e} \approx 1.444667

보다 큰 임의의 밑에 대해 잘 정의된다.

2. 2. 반복적 정의

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

:

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

2. 3. 초대수와의 관계

양의 실수에서 반복 로그는 연속 초대수(super-logarithm)의 천장 함수와 같다. 즉,

b

를 반복 로그의 밑으로 할 때,

n

이 구간

(^{y-1}b,\,^{y}b]

에 있으면, 반복 로그는

\log^*_b n = y

로 표시된다. 여기서

{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y

는 테트레이션이다. 단, 음의 실수

x

에 대해 반복 로그의 값은

\log^* x = 0

이지만,

\lceil \mathrm{slog}\,x \rceil = -1

이므로, 음의 실수에서는 앞서 제시한 관계가 성립하지 않는다.

3. 알고리즘 분석

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

3. 1. 예시

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

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

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

밑이 2인 반복 로그
x	log* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶]	5

3. 2. 성장 속도

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

밑이 2인 반복 로그
x	x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶]	5

더 큰 밑을 사용하면 반복 로그 값은 더 작아진다.

4. 기타 응용

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

5. 계산 복잡도 이론

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

참조

_[1] 서적 Introduction to Algorithms
_[2] 논문 Compaction of Church numerals
_[3] 논문 Randomization yields simple $O(n\log^\ast n)$ algorithms for difficult $\Omega(n)$ problems https://inria.hal.sc[...] 1992-03
_[4] 논문 Finding an approximate maximum https://web.math.pri[...] 1989-04
_[5] 논문 Deterministic coin tossing with applications to optimal parallel list ranking https://archive.org/[...] 1986-07
_[6] 간행물 Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001 IEEE Computer Society
_[7] 서적 Introduction to Algorithms
_[8] 논문 Randomization yields simple $O(n\log^\ast n)$ algorithms for difficult $\Omega(n)$ problems
_[9] 논문 Finding an approximate maximum
_[10] 논문 Deterministic coin tossing with applications to optimal parallel list ranking
_[11] 간행물 Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001 IEEE Computer Society
_[12] 논문 Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems. 1992
_[13] 논문 Finding an Approximate Maximum 1989
_[14] 논문 Deterministic coin tossing with applications to optimal parallel list ranking 1986
_[15] 서적 Introduction to Algorithms
_[16] 웹사이트 https://www.cs.princ[...]
_[17] 웹사이트 On Separators, Segregators and Time versus Space http://citeseerx.ist[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com