알고리즘 시간 복잡도, 마스터 정리

 

일반적으로 반복문 같은 경우에는 보는게 쉽다. 그냥 가장 큰 루프를 보면 되는데, 까다로운 것은 자기호출 함수가 있을 때 까다롭다. 그래서 수학 잘하는 형님들이 공식을 만들었는데

 

바로 마스터 정리이다. 증명하는 과정도 있는데 난 수학이 잼병이라 잘 모르겠다. 이렇게 좋은게 있다~~ 하고 쓰면 될 것 같다.

 

a: 재귀가 호출 된 수

b: 기존의 n보다 얼마나 쪼개는가.

c: 재귀가 아닌 것의 반복, 시간복잡도이다.

 

 

대표적인 합병 정렬을 예시로 보자.

a= 2 -> 재귀가 2번 호출 되므로

b=2 -> 재귀가 2로 나누어 지므로 mid =(low+high)/2

k= 1 -> merge과정은 시간 복잡도가 n이므로  구체적으로 따지면 n-1번 수행하게 되는데 그냥 편의상 n으로 봐도 무방하다.

 

그렇다면  T(n) = 2 * T(n/2) + n이 되는데 이를 마스터 정리에 대입하면 2 = 2^1, (a = b^k) 이므로 

T(n) = O(nlogn)이다.