[Journal] 반복로그 (log*)

서론

시간 복잡도 개념에 대한 탐구하던 중 log* 라는 기호를 가진 수학 기호를 발견하였다. 이것이 갖는 의미가 무엇인지 알아보고자 한다.

 

---

 

본론

컴퓨터 과학에서 n의 반복로그는 log* 라고 쓴다. 로그함수를 반복적으로 적용시켜 결과값이 1 이하가 될 때 까지 반복하는 함수이다. 수학적 정의는 아래와 같다.

Python을 이용해 간단하게 함수를 구현했다.

 

 

 

1에서 200까지의 반복로그와 로그 값을 그리는 프로그램이다. 로그는 최적화를 위해 외부 라이브러리에서 값을 가져왔고, 반복로그는 이를 이용해 함수로 구현했다. Matplotlib 라이브러리를 활용해 그래프를 시각화했다. 얻은 그래프는 아래와 같다.

 

 

보라색 그래프가 반복로그의 그래프이고, 파란색 그래프가 밑이 2인 로그함수의 그래프이다. 그래프를 통해 반복로그의 형태가 가우스함수와 유사하게 생겼다는 것을 확인할 수 있으며, 매우 느리게 증가한다는 사실도 확인할 수 있다. 실제로 밑이 2인 반복로그는 알고리즘에서 연산 가능한 모든 수에 대하여 5를 넘지 않는다.

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

---

 

마치며

 

복잡한 함수를 외부 프로그램을 이용하는 것이 아닌 Python으로 직접 구현 해 볼 수 있어 유익한 경험이었다. 교육과정 내에서 다루지 않는 다양한 함수가 존재하는 것을 알았고 이에 대해 더 찾아보려 한다.