분할 정복 재귀에 대한 고급 마스터 정리

Divide and Conquer는 문제를 비슷한 유형의 여러 하위 문제로 재귀적으로 분해하는 알고리즘으로, 이러한 하위 문제를 쉽게 해결할 수 있습니다.

Example

분할 정복 기법을 더 깊이 이해하기 위해 예를 들어 보겠습니다. -

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)은 다항식이 아닙니다.

이러한 경우에는 시간 복잡도를 찾는 마스터 정리가 핫 효율적이지 않으므로 재귀 재발에 대한 고급 마스터 정리는 의 재발 문제를 처리하도록 설계되었습니다. form −

T(n) = aT(n/b) + ø((n^k)logpn)

여기서 n은 문제의 크기입니다.

a = 재귀의 하위 문제 수, a > 0

n/b = 각 하위 문제의 크기 b > 1, k >= 0, p는 실수입니다.

이 유형의 문제를 해결하기 위해 다음 솔루션을 사용합니다.

• If a > b_k, then T(n) = ∅ (nlogba)
• If a = b_k, then
  • p > -1이면 T(n) = ∅(nlogba log^p+1n)
  • p = -1이면 T(n) = ∅(nlog_ba loglogn)
  • ba)
• a k이면
  • p > = 0이면 T(n) = ∅ (n) _klog_pn)
  • p

고급 마스터 알고리즘을 사용하여 일부 알고리즘의 복잡성을 계산합니다 −

이진 검색 − t(n) = θ(logn)

병합 정렬 − T(n) = θ(nlogn)

위 내용은 분할 정복 재귀에 대한 고급 마스터 정리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!