알고리즘25-2 Las Vegas vs Monte Carlo

 Las Vegas: 답은 항상 정확하지만 언제 끝나는지 왔다갔다한다.

 

Monte Carlo: 시간은 똑같지만 답이 맞을 때가 있고 틀릴 떄가 있다.

답이 항상 맞지 않아도 정확할 확률이 아주 높아야 한다,, 시간이 nlogn에 끝날 확률이 매우 높은 것처럼

 

 Las Vegas->Monte Carlo: 항상 가능

미리 시간을 딱 정해서 시간이 끝나면 아무 답이나 출력하는 방법이 있다.

시간은 정해져있고 가끔 맞고 가끔 틀리는 알고리즘으로 바뀐다.

 

Monte Carlo->Las Vegas: 바꿀 수 있지만 항상은 아님.

답이 나오면 그 답이 맞는 답인지 알 수 있는 경우가 있고 모르는 경우가 있다.

답을 푸는 것과 답이 맞는지 확인하는 것은 매우 다른 문제!

예를들어,

소인수분해 문제는 풀기는 어렵지만 확인은 쉬움

인수분해 문제도 마찬가지 axb=c

결론,

답을 확인하는 방법이 있다면 바꿀 수 있다.

답이 맞으면 끝내면되고 답이 맞지 않으면 또 돌린다. 맞힐 확률이 높으므로 조만간 맞추겠지

 

두 가지는 칼같이 구분되지 않고 한 쪽 방향으로 변환도 가능하다.

 

 

linked list안에 sorting된 상태

포인터가 아니고 배열 인덱스이다. 배열에 linked list들어가있음

순서대로 따라가므로 O(n) 시간이 걸린다.

배열로 찾아가도 O(n) 시간이 걸린다.

평균도 O(n)

 

1. 배열이니까 그중에 루트 n개를 아무거나 고른다.

linked list에서 아무거나 루트n개를 고른 것과 같다.

 

2. 골라진 애들을 쭉 보며 X보다 작은 애들 중 가장 큰 애를 고른다.

 

 

루트n = k

O(k+f(n,k)) 

k: 골라서 보는 시간

f(n,k): list 따라가는 시간

 

따라가는 distance가 d 이상이 될 확률 

정확히 표현하면 d일확률 = d이상일확률 - d+1이상일확률 

n-d개중에 k개가 골라져야 한다.

 

여기에서 골라지면 안되니까

 

 

따라서

= n / (k+1)

 

 

 

곱이 일정할 때는 대략 k가 같을 때(?)

k=루트n일때 가장 작아진다.

k도 루트n일때 f(n,k)도 대략 루트n이 된다.

 

평균적으로 루트n개일때 시간이 루트n정도 걸린다.

가끔 루트n이냐 대부분 루트n이냐?

 

루트 n개를 던져서 저 안에 아무것도 안나와야 한다.

 

100만중에 50만에 안들어가야 한다.

하나 던졌을 때 저 안에 안들어갈 확률은 1/2

1/2^50만 이므로 거의 0임

=> 루트n보다 많이 커질 확률은 거의 없음