Loading AI tools
위키백과, 무료 백과사전
컴퓨터 과학에서, n의 반복 로그(영어: iterated logarithm)는 log* n (보통 "로그-스타"(log star)이라고 읽는다)로 쓰며, 로그 함수를 반복적으로 적용시켜서 결과 값이 1보다 같거나 작아질 때까지 걸리는 횟수이다. 가장 간단한 정식 정의는 이 점화식의 결과이다.
양수에서, 연속적인 초-로그 (테트레이션의 역함수)는 본질적으로 동일하다.
하지만 음수에서는 로그-스타는 0이고 양의 x에 대해서 이므로 두 함수는 음수에서는 다르다.
계산 과학에서, 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]은 DTIME과 NTIME은 까지 다르다는 것을 보였다.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.