본문 바로가기
Algorithm

[Algorithm] Master Theorem (feat. Quick Selection)

by Saerong2 2020. 10. 23.

 

마스터 정리는 알고리즘을 재귀적인 점화식으로 표현하여 알고리즘의 동작시간을 점근적으로 계산할 수 있다는 정리입니다. 정해져있는 일종의 템플릿에 값만 넣으면 되기 때문에 계산하는 것이 어렵지 않지만 마스터 정리는 만능이 아니라  모든 재귀식에 대한 시간복잡도를 구할 수는 없습니다.

 

 

# Master Theorem

마스터 정리를 간단한 형태로 나타낸 것입니다. 여기서 a, b는 1보다 큰 양수이고, f(n)은 충분히 큰 n에 대해서 양의 함수값을 가져야 합니다.

 

자신의 알고리즘으로 위와 같은 점화식을 세웠다면, 점화식은 다음의 세 가지 중 한 가지를 반드시 만족하며 각각의 시간복잡도 T(n)은 아래와 같이 계산할 수 있습니다.

 

# Time Complexity of Quick Selection

이렇게만 보면 복잡해 보이니까 Quick Selection을 예시로 마스터 정리를 적용해 보겠습니다.

Quick Selection은 N개의 원소 중에서 K번째로 큰(또는 작은) 수를 알아내는 알고리즘으로, Avg는 Θ(N),  Worst는 O(N^2)으로 알려져 있습니다. Quick Selection은 Quick Sort와 마찬가지로 Partition( ) 내에서 피봇을 하나 (잘) 선택하고, 해당 피봇을 기준으로 왼쪽에는 피봇보다 작은 수들이, 오른쪽에는 피봇보다 큰 수들이 오도록 합니다. (정렬된 상태는 아니지요)

Quick Sort에 대한 배경지식이 없다면 아이디어는 어렵지 않으니 검색해 보시길 추천드립니다.

 

# Worst Case

worst case는 pivot이 언제나 배열의 한 쪽 끝으로 오는 경우입니다. partition이 0 : n-1개로 나뉘는 상태이고 이를 재귀적으로 표현하면 다음과 같습니다.

n개의 원소에 대해서 quick selection을 하는 큰 문제는 O(n)만큼의 시간이 걸렸고 n-1개의 원소에 대해서 quick selection을 재귀적으로 계속 해야합니다. 마스터 정리를 적용할 수 있을까요? 일단, a = 1, b = 1, f(n) = O(n)입니다. 그런데 log_1(1)은 0/0 과 같으니 정의되지 않은 값이네요. 따라서 마스터 정리를 이용하지 않고 다르게 접근해보도록 하겠습니다. 

이처럼, worst case는 T(n) = O(n^2)입니다.

 

# Average Case

마스터 정리에 대한 포스팅인데 정작 마스터 정리를 사용하지 못했네요.. Avg case에 대해서는 마스터 정리를 이용할 수 있길 바라며 한 번 재귀식을 세워봅시다.

평균적으로 피봇이 배열의 정 가운데에 온다고 해봅시다. Quick Sort의 경우 나누어진 파티션을 모두 재귀 호출 해야하지만 Quick Selection은 k번째 원소가 속한 partition에 대해서만 재귀를 호출합니다. 따라서 a = 1, b = 2, f(n) = O(n)입니다. (Quick Sort에서는 a = 2입니다.) 마스터 정리를 적용해보면 3번에 해당하는 것을 알 수 있습니다. 따라서 간단하게 T(n) = Θ(N) 임을 알 수 있습니다.

 

 

 

마스터 정리는 얼핏보면 복잡해 보이지만 점화식만 세울 수 있다면 a, b, f(x)를 단순히 대입하여 간단하게 시간복잡도를 구할 수 있었습니다. 하지만 모든 점화식에 대해 계산할 수 있는건 아니라는 거~ 기억해주세요. 연습삼아서 Quick Sort의 Average Case 대한 점화식을 세워보고 마스터 정리를 적용해 보시길 추천드립니다. (점화식은 사실 본문에 포함되어 있어요...!)

 

# References

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

https://ferrante.tistory.com/47

'Algorithm' 카테고리의 다른 글

[Algorithm] Heap Sort  (0) 2020.10.26
[Algorithm] Merge Sort  (0) 2020.10.24
[Algorithm] Quick Sort  (0) 2020.10.24
[Algorithm] Quick Selection  (0) 2020.10.23

댓글