Chapter 4. Randomized Algorithms (1)

Chapter :  CLRS 5, 7, 9.2, 10

 

1. Bogosort
2. Randomized Quicksort
3. Randomize Select
4. Majority Element
5. Direct Address Tables
6. Hash Tables
7. Hash Functions
8. Universal Hash Families
9. Open - Addressing

 

---

---

Randomized Algorithm (Monte Carlo vs. Las Vegas)

 

랜덤 알고리즘이란, 알고리즘 내 연산에 랜덤성이 들어가는 알고리즘입니다. 이  알고리즘은 기능 중 어디에 초점을 맞춰서 볼 건지에 따라 몬테 카를로인지, 라스 베가스 알고리즘인지 갈립니다.

 

라스 베가스 알고리즘은 정확성을 보장하지만, 실행 시간이 랜덤한 경우

몬테 카를로 알고리즘은 정확성이 랜덤이고, 실행시간은 일정할 경우 입니다.

 

이번 시간에는 라스베가스 알고리즘만 살펴 보겠지만

추후 Karger's algorithm 과 같은 알고리즘은 라스베가스 알고리즘이므로, 이런 알고리즘도 있음을 숙지하고 봐 주시길 바래요 :)

 

랜덤 알고리즘은 Running Time을 잴때 Worst Case Running Time 분석과 Expected Running Time 분석을 동시 채택함을 기억하고 구체적인 알고리즘 단계로 넘어갑시다.

 

---

BogoSort

 

def bogosort(A):
# Randomly permutes A until it's sorted
    while True:
    random.shuffle(A)
    sorted = True
    for i in range(len(A)-1):
    if A[i] > A[i+1]:
    sorted = False
    if sorted:
        return A

BogoSort는 그저 무작위로 섞어서 True인게 나올때까지 섞는 알고리즘입니다. 

 

Worst Case: O(∞)

최악의 경우 절때로 sorted된걸 뽑지 않을 수 있으니, 무한대로 흘러갈 수 있습니다.

 

Expected Running Time: O(n⋅n!)

전체 알고리즘 정렬의 가능성은 n! 이고, 이것 판별당 O(n) Time이 걸리므로 n⋅n! 시간이 걸린다.

 

 

---

Quicksort

 

저번에 Divide and Conquer 알고리즘에서 pivot을 고르는 알고리즘인 Selection 에 대해서 본 적이 있습니다.

 

Randomized QuickSort는 Pivot을 고릅니다. Pivot에 따라서 좌우를 정렬하는것을 반복하죠.알고리즘의 타당성 증명은 하지 않도록 하겠습니다.

def randomized_quicksort(A):
    if len(A) <= 1:
       return 
    pivot = random.choice(A)
    left, right = partition_about_pivt(A, pivot)
    randomized_quicksort(left)
    randomized_quicksort(right)

 

동작 예시

 

Expected running Time을 이제 한번 계산해봅시다.

 

X(a,b)를 a와 b가 Compare 된 횟수라고 합시다. (Ex: X(1,4) = 1 X(3,9) = 0)

 

이때, Σ Σ X(a,b)가 바로 Runtime이 됩니다.

 

이것을 이제 확률 기반으로 본다면 Σ Σ E[X(a,b)] 로 나타낼 수 있습니다. 

그렇다면 이제, E[X(a,b)]를 구해 볼까요?

 

E[X(a,b)] = P(X(a,b) = 1)⋅1 + P(X(a,b) = 0)⋅0 = P(X(a,b) = 1)

 

X(a,b)가 0이 되려면 pivot이 a와 b 사이에 있어야 합니다.  (계산이 용이하도록 하기 위해 a,b element를 a번째 b번째 element로 합시다.)

 

이 말은 X(a,b)가 1이 되려면 b - a + 1길이의 구간에서 pivot이 a 혹은 b가 되면 된다는 뜻입니다.

이제, Σ Σ E[X(a,b)] 를 구해 봅시다.

고로 Quicksort의 Expected Running Time은 n log n 입니다.

 

---

Better Partitioning

 

Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - YouTube

Partition을 더 잘 해볼까요?

 

---

QuickSort vs MergeSort

 

Running time	Worst-case: O(n2 ) Expected: O(n log(n))	Worst-case: O(n log(n))
Used by	Java for primitive types C qsort Unix g++	Java for objects Perl
In-Place? (With O(log(n)) extra memory)	Yes, pretty easily	Not easily* if you want to maintain both stability and runtime. (But pretty easily if you can sacrifice runtime).
Stable	No	Yes