스털링 근사 편집하기

스털링 근사(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 값에 대해 실제 값과 기본 스털링 근사 및 보정된 스털링 근사 값을 비교한 것이다.
{| class="wikitable"
|+계승 값과 스털링 근사의 비교
|-
!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!을 근사적으로 다룰 때 사용
==같이 보기==
*[[알고리즘 복잡도]]