상위 질문
타임라인
채팅
관점

반복 로그

위키백과, 무료 백과사전

반복 로그
Remove ads

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

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

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

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

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

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

Remove ads

알고리즘 분석

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

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

자세한 정보 x, lg* x ...

밑이 더 크면 반복 로그의 횟수가 줄어든다. 당연히도, 복잡도 이론에서 일반적으로 사용하는 더 느리게 증가하는 유일한 함수는 역 아커만 함수이다.

Remove ads

다른 적용

반복 로그는 symmetric level-index arithmetic에서 쓰이는 generalized logarithm function과 밀접하게 관련되어 있다. 또한, 어떤 숫자를 그 숫자의 각 자릿수를 더한 값으로 바꿔써서 자릿수근에 도달하기까지 걸리는 횟수인 덧셈 지속성에 비례한다.

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

Remove ads

참고 문헌

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads