스털링 근사

스털링 근사(Sterling's Approximation)는 계승(factorial) 함수 n!을 근사적으로 표현하는 공식이다. 특히, 큰 n에 대해 계산할 때 유용하며, 알고리즘 분석과 확률 이론에서 자주 사용된다.

개요

n! (n 계승)은 다음과 같이 정의된다.

• n! = n × (n-1) × (n-2) × ... × 1

그러나, n이 클 때 직접 계산하는 것은 비효율적이므로, 스털링 근사를 사용하여 근삿값을 구할 수 있다. 스털링 근사는 로그 함수와 연속적인 근사를 이용하여 계승 값을 표현한다.

스털링 근사 공식

스털링 근사의 기본 형태는 다음과 같다.

• n! ≈ √(2πn) × (n/e)ⁿ
• 

이 식을 로그를 이용하여 변형하면:

• ln(n!) ≈ n ln(n) - n + (1/2)ln(2πn)
• 

이 공식은 n이 클 때 매우 정확한 값을 제공한다.

보정된 스털링 근사

보다 정밀한 근사를 위해 추가적인 보정항을 사용할 수 있다.

• n! ≈ √(2πn) × (n/e)ⁿ × e^(1/12n)
• 

보정된 근사는 기본 스털링 근사보다 더 높은 정확도를 제공하며, 특히 작은 n에서도 상대 오차가 줄어든다.

스털링 근사의 정확도

스털링 근사는 큰 n일수록 오차가 감소하며 정확도가 높아진다. 아래 표는 몇 개의 n 값에 대해 실제 값과 기본 스털링 근사 및 보정된 스털링 근사 값을 비교한 것이다.

계승 값과 스털링 근사의 비교

n	실제 값 (n!)	스털링 근사	상대 오차(%)	보정된 스털링 근사	보정된 상대 오차(%)
1	1	0.922	7.79	1.002	0.23
2	2	1.919	4.05	2.001	0.03
3	6	5.836	2.73	6.001	0.01
5	120	118.019	1.65	120.003	0.002
10	3,628,800	3,598,695	0.83	3,628,810	0.0003

스털링 근사의 응용

스털링 근사는 다음과 같은 분야에서 활용된다.

• 알고리즘 분석 - 계승 함수가 포함된 시간 복잡도 계산 (예: O(n!))
• 확률 이론 - 조합(combination) 및 확률 분포의 근사 계산
• 정보 이론 - 엔트로피 계산에서 n!을 근사적으로 다룰 때 사용

같이 보기

• 알고리즘 복잡도