반복 로그

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

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

하지만 음수에서는 로그-스타는 0이고 양의 x에 대해서 이므로 두 함수는 음수에서는 다르다.

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

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

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

 유클리드 최소 신장 트리를 아는 점들의 집합에서 델로네 삼각분할을 찾기: 무작위적O(n  n) 시간Olivier Devillers, "Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.". International Journal of Computational Geometry & Applications 2:01 (1992), pp. 97–111.
 정수 곱셈에서의 퓨러 알고리즘: O(n log n 2O( n))
 추정 최댓값을 찾기(적어도 중앙값보다 큰 원소):  n − 4 to  n + 2 병렬 연산Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267.
 리차드 콜(Richard Cole)과 우지 비슈킨(Uzi Vishkin)의 n-순환 그래프의 3색 색칠에 대한 분산 알고리즘: O( n) 동기 통신 라운드.Richard Cole and Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53. Section 30.5.
 경로 압축을 한 weighted quick-unionhttps://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

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

 x   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과 밀접하게 관련되어 있다. 또한, 어떤 숫자를 그 숫자의 각 자릿수를 더한 값으로 바꿔써서 자릿수근에 도달하기까지 걸리는 횟수인 덧셈 지속성에 비례한다.

산다남On Separators, Segregators and Time versus Space은 DTIME과 NTIME은 까지 다르다는 것을 보였다.

참고 문헌

분류:점근 해석
분류:로그