스털링 근사

스털링 근사 (Stirling’s Approximation) 는 팩토리얼 값이나 감마함수 값을 쉽고 빠르게 근사하기 위한 방법입니다.

$$ \ln{(N !)} \approx N \ln{N} - N $$

$\ln{n}$은 자연로그함수 입니다.
팩토리얼 값의 계산은 정말 $1$부터 $N$까지 곱해보는 방법밖에 없지만 로그값은 더 빠르게 구할 수 있습니다.
이는 다음과 같은 과정으로 구할 수 있습니다.

스털링 근사 과정

로그함수의 성질 $\ln{(ab)} = \ln{a} + \ln{b}$ 에 의해서

$$ \ln(N !) = \sum_{k = 1}^{N} \ln{k} $$

이다. 이때, 합과 적분의 관계에 의해 $\sum\limits_{k = 1}^{N} \ln{k} \approx \int_{1}^{N} \ln{x} \, dx$이고, 부분적분을 이용해 로그함수를 적분해주면
$$ \int^{N}_{1} \ln{x} \, dx = N \ln{N} - N + 1 $$ 이므로, $\ln(N !) \approx N \ln{N} - N$으로 근사시킬 수 있다. (상수는 무시할 수 있습니다.)

굉장히 디테일한 근사로는 $n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^{n} \left(1 + \frac{1}{12n} + \frac{1}{288 n^{2}} + \cdots \right)$로 할 수 있습니다. $\pi$는 원주율 $\pi$ , $e$는 자연로그의 밑 $e$ 입니다.
팩토리얼이 지수함수보다 더 빠르게 증가한다는 것을 알 수 있습니다.