확률적 알고리즘

결론

확률적 알고리즘 (랜덤 알고리즘)

:난수를 사용하는 알고리즘 

1.몬테카를로 알고리즘 : 정확성 보장 x 속도 빠름

2.라스베가스 알고리즘 : 정확성 보장 0 속도 느릴수도

 

---------

확률적 알고리즘이라고 해서 여러 통계학적 sharp하고 mathmatical한 기법들을 사용하는줄 알았는데

저 두개의 예를 보니깐 그저 난수를 사용하는거였다. 물론 난수라는것이 무작위라는 면에서 통계적이라고 할수있겠다.

 

몬테카를로 알고리즘 //

원 주율 구하기 (반지름 1 ,

원의 사분의 일

난수로 사각형안에 점을 찍음 

전체 점 : 100 원안에 들어온 점:80

파이/4 = 80/100          이런식으로 구함

중간값보다 큰값 구하기

무작위로 k개 뽑아서 그중 큰값이 중간값보다 클확률

1개 : 1 - 1/2 

2개 : 1 - (1/2)^2

....

k개 : 1 - (1/2)^k

 

 

라스베가스 알고리즘//

정확성은 보장하지만 시간은 보장하지 못한다고 한다.

예제는 ..