Master Theorem 마스터 정리 알고리즘 시간 복잡도 구하기 (최대한 쉽게)
알고리즘 과제로 master theorem으로 T(n)에 대한 시간복잡도를 구하는 문제가 있어서 구글링 해봤는데
수포자인 내가 봤을땐 정말 하나도 이해되지 않았다.
점화식을 뭘 어떻게 해서 등비수열..뭐?
정말 모르겠어서 chat gpt에게 쉽게 설명해달라고 했다.
그리고 내가 과제를 풀기 위해 이해한 것만 적어본다
원래의 그 증명이야 당연히 이해가 안되고 그냥 푸는것도 어렵..
주의) 일부문제에만 적용될 수도 있다.
우린 여기서 a,b,d 값을 구해 case 1, 2, 3 중 어디에 해당하는지 알아내면 된다.
단, f(n)이 nlogn인 경우는 d로 직접 표현할 수 없다.
예시 문제 2개를 보며 풀어보자.
여기서 a = 2, b = 2, log_b(a)= 1, 그럼 d는 뭘까?
f(n)의 형태가 n의 몇 제곱인가를 찾는게 핵심이다.
f(n) = 2 , 2는 상수이므로 O(n^0) 즉 d = 0 (b^d = 1)
case에 비교해보면, a > b^d <=> log_b(a) > d 인 case 3에 맞다.
확인) 2 > 1 <=> 1 > 0 만족.
따라서 형태가 O(n^log_b*a)형태가 되는데 여기서 log_b(a) = 1 이었으니
O(n^1) = O(n)이 된다.
따라서 문제 1의 시간 복잡도는 O(n)이다.
2.
여기서 a = 3, b = 2 , log_b(a) = 1.548, d는?
엥 이번엔 f(n)이 n^2이다. 상수의 형태가 아닌데 어떻게 구하지?
이때 d는 그냥 이 지수 값을 의미한다.
즉, f(n) = n^2 -> d = 2 (b^d = 4)
case 1에 만족한다는 것을 알 수 있다.
확인) 3 < 4 <=> 1.548 < 2
따라서 형태가 T(n^d)가 되는데 d = 2이니 O(n^2)가 된다.
문제 2의 시간 복잡도는 O(n^2)이다.
(이 글은 개인 기록용으로 작성되었습니다)
정말 쉽게 푼 만큼 이렇게 간단하지 않은 문제엔 적용이 안될 수도 있다. 그리고 이게 틀린 걸 수도 있다. 다른 분들이 설명한 것과 같이 보면서 이해해보시기 바랍니다.
