마스터 정리(Master Theorem)는 분할 정복 알고리즘 분석에서 발생하는 반복 관계를 해결하는 데 사용되는 도구입니다. 마스터 정리는 다음 형식의 반복 관계를 푸는 체계적인 방법을 제공합니다.

T(n) = aT(n/b) + f(n)

1. 여기서 a, b, f(n)은 양의 함수이고 n은 문제의 크기입니다. 마스터 정리는 일부 상수 k에 대해 반복의 해법이 O(n^k) 형태가 되는 조건을 제공하고 k 값을 결정하기 위한 공식을 제공합니다.
2. 마스터 정리의 고급 버전은 기본 형식보다 더 복잡한 순환 관계를 처리할 수 있는 보다 일반적인 형식의 정리를 제공합니다. 마스터 정리의 고급 버전은 여러 용어와 더 복잡한 함수를 사용하여 반복을 처리할 수 있습니다.
3. 마스터 정리가 모든 재발 관계에 적용되는 것은 아니며 주어진 재발에 대해 항상 정확한 솔루션을 제공하지 않을 수도 있다는 점에 유의하는 것이 중요합니다. 그러나 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 유용한 도구이며 더 복잡한 반복 문제를 해결하기 위한 좋은 출발점을 제공합니다.

마스터 정리는 점근적 표기법으로 알고리즘(분할 및 정복 알고리즘)의 실행 시간을 결정하는 데 사용됩니다.
재귀를 사용하여 해결되는 문제를 생각해 보세요.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

위의 알고리즘은 문제를 다음과 같이 나눕니다. ㅏ 각각 크기가 n/b인 하위 문제를 재귀적으로 풀어 문제를 계산하고 문제에 대해 수행된 추가 작업은 f(n), 즉 위 절차에서 하위 문제를 생성하고 결과를 결합하는 데 걸리는 시간입니다.

따라서 마스터 정리에 따르면 위 알고리즘의 런타임은 다음과 같이 표현될 수 있습니다.

 T(n) = aT(n/b) + f(n)>

여기서 n = 문제의 크기
a = 재귀의 하위 문제 수 및 a>= 1
n/b = 각 하위 문제의 크기
f(n) = 하위 문제로 나누는 등 재귀 호출 외부에서 수행되는 작업 비용 및 솔루션을 얻기 위해 이를 결합하는 비용.

모든 재발 관계가 마스터 정리를 사용하여 풀 수 있는 것은 아닙니다. 즉, 다음과 같습니다.

• T(n)은 단조롭지 않습니다. 예: T(n) = sin n
• f(n)은 다항식이 아닙니다. 예: T(n) = 2T(n/2) + 2^N

이 정리는 반복이 다음 형식인 경우 분할 정복 알고리즘의 실행 시간을 결정하는 데 사용할 수 있는 마스터 정리의 고급 버전입니다.

여기서 n = 문제의 크기
a = 재귀의 하위 문제 수 및 a>= 1
n/b = 각 하위 문제의 크기
b> 1, k>= 0이고 p는 실수입니다.

그 다음에,

1. 만약 a> b라면^케이, 그러면 T(n) = θ(n^{통나무_비ㅏ})
2. 만약 a = b라면^케이, 그 다음에
   (a) p> -1이면 T(n) = θ(n^{통나무_비ㅏ}통나무^p+1N)
   (b) p = -1이면 T(n) = θ(n^{통나무_비ㅏ}로그로그인)
   (c) p <-1이면 T(n) = θ(n^{통나무_비ㅏ})
   
3. 만약 케이, 그럼
   (a) p>= 0이면 T(n) = θ(n^케이통나무^피N)
   (b) p<0이면 T(n) = θ(n)^케이)
   

시간 복잡도 분석 –

예제-1: 이진 검색 – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 및 p = 0
비^케이= 1. 따라서 a = b^케이그리고 p> -1 [사례 2.(a)]
T(n) = θ(n^{통나무_비ㅏ}통나무^p+1N)
T(n) = θ(logn) 예-2: 병합 정렬 – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
비^케이= 2. 따라서 a = b^케이그리고 p> -1 [사례 2.(a)]
T(n) = θ(n^{통나무_비ㅏ}통나무^p+1N)
T(n) = θ(nlogn) 예-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
비^케이= 4. 그래서, k 및 p = 0 [사례 3.(a)]
T(n) = θ(n^케이통나무^피N)
T(n) = θ(n²)

예시-4: T(n) = 3T(n/2) + 로그²N
a = 3, b = 2, k = 0, p = 2
비^케이= 1. 따라서 a> b^케이[사례 1]
T(n) = θ(n^{통나무_비ㅏ})
T(n) = θ(n^{통나무₂삼})

예제-5: T(n) = 2T(n/2) + nlog²N
a = 2, b = 2, k = 1, p = 2
비^케이= 2. 따라서 a = b^케이[사례 2.(a)]
T(n) = θ(n^{통나무_비ㅏ}통나무^p+1N )
T(n) = θ(n^{통나무₂2}통나무^삼N)
T(n) = θ(nlog^삼N)

예제-6: T(n) = 2^N티(n/2) + n^N
이 반복은 함수가 T(n) = aT(n/b) + θ(n 형식이 아니기 때문에 위 방법을 사용하여 풀 수 없습니다.^케이통나무^피N)

GATE 연습 문제 –

• GATE-CS-2017 (세트 2) | 질문 56
• 게이트 IT 2008 | 질문 42
• 게이트 CS 2009 | 질문 35

마스터 정리와 관련하여 명심해야 할 몇 가지 중요한 사항은 다음과 같습니다.

1. 분할 정복 재발: 마스터 정리는 분할 정복 알고리즘 분석에서 발생하는 반복 관계를 풀기 위해 특별히 설계되었습니다.
2. 재발 형태: 마스터 정리는 T(n) = aT(n/b) + f(n) 형식의 재발 관계에 적용됩니다. 여기서 a, b 및 f(n)은 양의 함수이고 n은 크기입니다. 문제의.
3. 시간 복잡도: 마스터 정리는 일부 상수 k에 대해 반복의 해법이 O(n^k) 형태가 되는 조건을 제공하고 k 값을 결정하기 위한 공식을 제공합니다.
4. 고급 버전: 마스터 정리의 고급 버전은 기본 형식보다 더 복잡한 순환 관계를 처리할 수 있는 보다 일반적인 형식의 정리를 제공합니다.
5. 제한 사항: 마스터 정리는 모든 재발 관계에 적용할 수 없으며 주어진 재발에 대해 항상 정확한 솔루션을 제공하지 않을 수도 있습니다.
6. 유용한 도구: 한계에도 불구하고 마스터 정리는 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 유용한 도구이며 보다 복잡한 반복 문제를 해결하기 위한 좋은 출발점을 제공합니다.
7. 다른 기법으로 보완: 어떤 경우에는 주어진 반복 관계를 완전히 풀기 위해 대체법이나 반복법과 같은 다른 기법으로 마스터 정리를 보완해야 할 수도 있습니다.