분할 및 정복 쉽게 풀 수 있는 유사한 유형의 여러 하위 문제로 재귀적으로 분기하는 문제를 기반으로 하는 패러다임에서 작동하는 알고리즘입니다.
예시
분할 정복 기법에 대해 자세히 알아보기 위해 예를 들어 보겠습니다. −
function recursive(input x size n) if(n < k) Divide the input into m subproblems of size n/p. and call f recursively of each sub problem else Solve x and return
모든 하위 문제의 결과를 결합하고 원래 문제에 대한 솔루션을 반환합니다.
설명 − 위의 문제에서 문제 세트는 쉽게 해결할 수 있는 더 작은 하위 문제로 세분화됩니다.
분할과 정복을 위한 마스터스 정리 재귀 관계 알고리즘에 대한 빅 0 값을 결정하는 데 사용할 수 있는 분석 정리입니다. 알고리즘에 필요한 시간을 구하여 점근적 표기 형태로 나타내기 위해 사용합니다.
위의 예에서 문제의 런타임 값의 예 -
T(n) = f(n) + m.T(n/p)
대부분의 재귀 알고리즘에 대해 마스터의 정리를 사용하여 알고리즘에 대한 시간 복잡도를 찾을 수 있지만 일부 경우 마스터의 정리가 적용되지 않을 수 있습니다. 이것은 마스터의 정리가 적용되지 않는 경우입니다. 문제 T(n)이 단조롭지 않은 경우(예:T(n) =sin n). 문제 함수 f(n)은 다항식이 아닙니다.
이러한 경우 시간 복잡도를 찾는 마스터 정리가 효율적이지 않기 때문에 재귀 반복을 위한 고급 마스터 정리가 설계되었습니다. −
형식의 반복 문제를 처리하는 디자인입니다.T(n) = aT(n/b) + ø((n^k)logpn)
여기서 n은 문제의 크기입니다.
a =재귀의 하위 문제 수, a> 0
n/b =각 하위 문제의 크기 b> 1, k>=0이고 p는 실수입니다.
이러한 유형의 문제를 해결하기 위해 다음 솔루션을 사용합니다.
- 만약>bk , T(n) =∅(nlogba)
- a =bk인 경우 , 그럼
- p> -1이면 T(n) =∅(nlogba log p+1 n)
- p =-1이면 T(n) =∅(nlogba loglogn)
- p <-1이면 T(n) =∅(nlogba )
- 만약
- p> =0이면 T(n)=∅(nk 로그p n)
- p<0이면 T(n) =∅(nk)
고급 마스터 알고리즘을 사용하여 일부 알고리즘의 복잡성을 계산합니다.
이진 검색 − t(n) =θ(logn)
병합 정렬 − T(n) =θ(nlogn)