반복 로그

(반복로그에서 넘어옴)

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

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

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

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

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

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

알고리즘 분석

편집

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

반복 로그는 로그보다도 더 느리게 증가한다. 실제로 수행한 알고리즘의 실행시간의 계에 관련된 모든 n값에 대해서(즉, n ≤ 265536으로 265536은 알려진 우주의 원자의 개수의 추정치보다 훨씬 크다), 밑이 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과 밀접하게 관련되어 있다. 또한, 어떤 숫자를 그 숫자의 각 자릿수를 더한 값으로 바꿔써서 자릿수근에 도달하기까지 걸리는 횟수인 덧셈 지속성에 비례한다.

산다남[6]DTIMENTIME 까지 다르다는 것을 보였다.

참고 문헌

편집
  1. 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.
  2. Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267.
  3. Richard Cole and Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.
  4. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). 《Introduction to Algorithms》 1판. MIT Press and McGraw-Hill. ISBN 0-262-03141-8.  Section 30.5.
  5. https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
  6. On Separators, Segregators and Time versus Space