namuid(r7 판)

[주의!] 문서의 이전 버전(2025-05-08 21:59:33에 수정)을 보고 있습니다. 최신 버전으로 이동

이 문서는 분류가 되어 있지 않습니다. 분류:분류에서 적절한 분류를 찾아 문서를 분류해주세요!

유니코드 기준 현대 한글의 모든 완성형 글자는 총

19 \times 21 \times 28 = 11,172

자이며,

6

개의 문자가 연달아 사용되므로 표본 공간의 크기는

11,172^6 = 1,944,399,775,118,767,509,471,232 \approx 1.9443997751 \times 10^{24}

입니다. 편의상 이를

N

라고 하겠습니다.

구하고자 하는

p

는 '동일 작업에서 최소 하나의 식별자 충돌이 발생할 확률'입니다. 이를

p = 0.1\%

라고 두고 테일러 전개로 필요한 표본의 수

k

의 하한을 근사해 봅시다. 일단 자명하게

p = 1 - \dfrac{_N\mathrm P_k}{N^k}

이므로 어떤 함수

f

에 대해

f(k) \leq 1 - p

를 성립시키는 가장 작은

k

를 근사하면 됩니다. 우선 위에 쓴

p

를 구하는 수식을 곱의 형태로 정리해 봅시다.

\displaystyle 1 - p = \prod^{k-1}_{i = 1} 1 - \dfrac iN

이어서

e^{-\frac kN}

를 테일러 전개하고 선형 근사를 구하면

\displaystyle e^{-\frac kN} = \sum_{i = 0} \dfrac{\left(-\dfrac kN\right)^i}{i!} \approx 1 - \dfrac kN

이 근사를 적용해서 '어떤 함수'

f

가

1 - p

를 근사하도록 조립해 봅시다.

\displaystyle f(N) = e^{-\dfrac{k(k-1)}{2N}} = \prod^{k - 1}_{i = 1} e^{-\dfrac{i}N}

k > 62,375,838,650 = 6.237583865 \times 10^{10}