namuid(비교)

==# 버림 #==

보기 편하게 로그 형태로 전개하면 다음과 같이 [math(x)]에 대한 이차방정식이 나옵니다. 편의상 [math(f(x))]를 [math(y)]라고 두었습니다.

||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle x^2 - x + 2N \ln y= 0)]||

방정식을 풀면 역함수를 구할 수 있겠군요. 시행 횟수 [math(x)]는 양의 정수임이 자명하니 음수근은 버리겠습니다.

||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle f^{-1}(y) = x = \frac12 + \sqrt{\frac14 - 2N \ln y})]||

보다시피 이 함수 [math(f^{-1})]에 찾고자 하는 충돌 확률 [math(1 - p)]를 넣으면 이를 만족시키는 [math(x)]의 근사값을 구할 수 있습니다. 앞서 [math(p = 0.1\% = 10^{-3})]로 주었으므로

||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle\begin{aligned}

x &= \frac12 + \sqrt{\frac14 - 2N \ln 0.999} \\

&= 5,583,229.881461706 \\

&\approx 5.5832298814617 \times 10^6 \\

\end{aligned})]||

다시 말하면 한번에 5백만개 정도의 문서를 편집하는 경우 [math(0.1\%)] 정도의 충돌 가능성이 있을 수 있다는 소리입니다.

반면에 [[https://namu.wiki/w/나무위키:통계|나무위키:통계]]에 따르면 2025-05-08 20:04:05-0400 기준 나무위키의 모든 문서는 [math(7,149,087)]개에 불과합니다.