ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 확률적 알고리즘
    Algorithm 2020. 7. 4. 18:12

    결론

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

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

    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

     

     

    라스베가스 알고리즘//

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

    예제는 ..

     

    'Algorithm' 카테고리의 다른 글

    Animation Test  (0) 2020.07.24
    [CS_Essential_Algorithms] 개요  (0) 2020.07.20
    String Matching Algorithm 종류  (0) 2020.07.08
    [전역 최적화] Genetic_Algorithm  (0) 2020.07.05
    탐색의 종류  (0) 2020.06.22
Designed by Tistory.