스털링 근사 (Stirling's approximation)

스털링 근사 (Stirling's approximation)

 

수학에서 스털링 근사(영어: Stirling’s approximation) 또는 스털링 공식(영어: Stirling’s formula)은 큰 계승을 구하는 근사법이다. 나아가 실수와 복소수까지 확장시켜 감마 함수에 대한 근삿값을 구할 수 있도록 한다.

 

계승(팩토리얼: factorial)이란 기호로 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다.

일반적으로 확률과 통계, 수학 과목에서는 n! = 1×2×3×⋯⋯×(n−1)×n 으로 배운다. (n부터 1씩 빼면서 곱하는 것)

 

아래 표는 20까지의 팩토리얼 값을 정리한 것이다. 이처럼 n이 커질 수록 해당 값이 기하급수적으로 증가하게 되는데 이 때 스털링의 근사식을 응용할 수 있다.

0!	1
1!	1
2!	2
3!	6
4!	24
5!	120
6!	720
7!	5 040
8!	40 320
9!	362 880
10!	3 628 800
11!	39 916 800
12!	479 001 600
13!	6 227 020 800
14!	87 178 291 200
15!	1 307 674 368 000
16!	20 922 789 888 000
17!	355 687 428 096 000
18!	6 402 373 705 728 000
19!	121 645 100 408 832 000
20!	2 432 902 008 176 640 000

스털링 공식(Stirling's formula)

이 근사는 큰 수에 대한 팩토리얼의 계산이라는 측면에서 유용하다. 열열학, 통계역학과 같은 분야에선 많은 수의 분자를 가정하기 때문에 필수적이며, n!에 대한 다음과 같은 근사식을 얻을 수 있다.

이는 비교 정렬(Comparison Sort)에서 최악의 경우 수행 시간이 절대  Ω(nlgn)을 밑돌 수 없다는 것을 증명해 줄 수 있다.

결정 트리 모델에서 리프 노드가 n!개 있을 때, 최악의 상황은 가장 깊은 리프 노드까지 내려가는 것이다.

n!개의 리프노드를 가진 트리의 높이는 log2n! 은 되어야 하므로 스털링의 근사식의 결론을 이용하면 적어도 Ω(nlgn)이다.