Randomized Algorithm

728x90

랜덤에 대한 간단한 이야기

항공 모함에 비행기가 착륙할 때, 줄에 걸려서 착륙하게 되어있다. 이 줄에 잘 걸리는 비행기와 잘 걸리지 않는 비행기가 존재하기 때문에 이 줄의 간격을 다양하게 한다.

Randomized QuickSort

Quicksort? pivot을 잡은 후, pivot보다 작은 값과 pivot보다 큰 값으로 나눠 생각하는 것

For any deterministic QuickSort Alogrithm there exist Classes of Inputs which the Algorithm takes O(N\(^2\)) Time
The Average was taken over all possible inputs
All my inputs could be in the class
can you make the situation better?
it all depends on the pivot -> Select random pivot!

랜덤한 입력을 준 것의 평균을 보면 merge보다 quick sort가 더 빠르다

그렇지만, 내가 사용한 데이터는 quick sort가 느릴 수 있다.

Worst case : O(N\(^2\))

Best case : O(N log N)

Randomized : All Possible Cases with Same Probability -> 특정한 고정된 입력에 대해 평균적인 성능

E(n) = \(\frac{1}{n}\sum^n_{n=1}[E(k-1) + E(n-k)]\)

특정한 입력에 대해서도 돌아간다 (랜덤한 원소를 pivot)

n개를 sorting할 때 걸리는 시간의 기댓값

저번에 본 것은 모든 가능한 n에 대한것

랜덤한 것이기 때문에 1/n, pivot은 1부터 n까지 각 값일 기댓값을 곱한다.

따라서 E(n) = O(n log n)

Las Vegas : Always Correct, Running Time Probabilistic 항상 정확하다, 실행 시간이 확률적
Monte Carlo : Probabilistically Correct, Always the same time 확률적으로 정확함, 항상 같은 시간
Las Vegas -> Monte Carlo : Stop Running if Time exceeds Limit and output incorrect Answer
만약 시간이 다 되면 끊고 부정확한 answer을 내보냄
Monte Carlo -> Las Vegas : You Need Verifier (that checks the Answer for Correctness), does no always exist / Repeat until Answer is Correct
verifier을 이용하여 답이 맞는지 틀린지 반복함

List는 sorting이 되어있다 (화살표를 따라가면 더 큰 값이 있음)

배열을 보면 sorting이 되어있지 않다.

링크를 따라가도 O(n), 배열을 봐도 O(n)

Assum k members are selected
Let time be O(k + f(n,k)) -> f(n,k) 아직 계산하지 못한 부분
Calculate f(n,k), probability of distance being d = \(\frac{n-d}{n}^k\) - \(\frac{n-d-1}{n}^k\)

거리가 정확히 d일 확률을 생각해야한다

앞 위에 각각 a개 b개가 있다고 생각하면, a+b = n-d이다

거리가 d 이상일 확률에서 d+1 이상일 확률을 빼면 된다.

f(n,k) = \(\sum^{n-1}_{d=1} d((\frac{n-d}{n}^k - (\frac{n-d-1}{n})^k)\) = \(k + \frac{n}{k+1}\)

Best when k = \(\sqrt{n}\)

728x90