Randomized Algorithm - Linked List in an Array (Las Vegas)

Linked List in an Array (Las Vegas)

• 링크드 리스트에서 x 찾기
• 기존 링크드 리스트는 O(n)

1. 배열에서 루트n개를 랜덤하게 고른다.
2. 골라진 애들중 X보다 작은애들을 고른다.
3. 작은 애들중 가장 큰 애 Y를 고른다.
4. Y의 링크를 타면서 간다.

기댓값 계산 및 검증

배열에서 k개를 골랐다고 가정했을 때 O(k + f(n, k))가 걸린다.
f(n, k) 는 Y와 x 사이의 거리가 d일 확률의 기댓값이다.
P[D=d] = P[D≤d] - P[D≤d-1] 이므로
=((n-d)/n)^k - ((n-d-1)/n)^k
따라서 기댓값 f(n, k) = sigma_{d=1}^{n} d * P[D=d] 이다.

즉, k + f(n, k) = k + n/(k+1) 이므로 대략 k =√n 일때 가장 최적이다.
O(√n)이 나온다.

d가 커지더라도,√n개나 고르기 때문에 d가 클수록√n개도 커진다.
따라서 d가 어느정도 커지면 많이 고르는 만큼 그 안쪽에서 골라질 확률이 높아지므로
d는 어느정도 커지기 힘들다.