마스터 정리를 적용 할 수없는 이유

Question

과제 수행 중 몇 가지 질문에 답했습니다.

1. T (N) = T (2N/5) + N
2. T (N) = T (2N/3) + T (N/3) + N
3. T (N) = (N-2) + n

어떤 것이 든 마스터 정리를 적용 할 수 없다는 것을 알 수 있습니다. 하지만 왜? 그리고 그들의 상한은 무엇입니까 (큰 - 오)?

Answer 1

마스터 정리 폼의 재발에

T (N) = (AT N/b) + O (N ^D)

을 적용 할 수있다 b 및 d는 상수이다. (몇 가지 다른 공식이 있지만 위의 경우는 일반적인 경우를 처리합니다). 특히이

• 문제 크기
• 는 하위 문제 일정한 곳이어야
• 하위 문제는 모두 동일한 크기를 가져야 일정한 비율로 축소되어
• 한다는 것을 의미 덧셈 항은 다항식이어야합니다.

이러한 기준은 두 번째 반복 (하위 문제는 동일한 크기가 아님)과 세 번째 문제 (문제 크기는 상수 요인으로 축소되어야 함)를 배제합니다. 그러나 첫 번째 재발은이 네 가지 기준 모두를 충족시킵니다. 재발생을

T (n) = T (n/(5/2)) + n으로 재 작성하는 것이 도움이 될 수 있습니다.

이것을 바탕으로 마스터 정리의 어떤 경우에 있으며 재발은 어떻게 해결됩니까?

Answer 2

마스터 방법은 다음 유형의 되풀이에만 작동합니다. 질문 내용

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1 

,

1. T (N) = T (2N/5) + N

는 @templatetypedef 이미 같이 마스터 정리 맞게이 반복 식을 수정 한

T(n) = T(n/(5/2)) + n 

여기에서 해결할 수 있습니다.

2. T (N) = T (2N/3) + T (N/3) + N

분명히 이것은 마스터 정리하여 해결 될 수 없다. 우리는 재귀 트리를 만들고 시도해야합니다. 재귀 트리는 재귀 호출 트리와 각 호출에서 수행 된 작업량을 다이어그램으로 보여줍니다. 따르는 그래서 here

에서 촬영 화상이며, 이것은 (N * N 로그)

3. T (N) = T (N-2) + N O로 줄일

분명히 이것은 마스터 정리로 직접 해결할 수 없습니다. Subtract-and-Conquer 형식에 대해 수정 된 수식이 있습니다.

이 link이 유용 할 수 있습니다. 다음

형태의 재발 들어

,

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

where n > 1, a>0, b>0 

F (N)가 O 인 경우 (N ^K)이고, k> = 0,

1. 만약 < 한 후, T (N) = O (N ^K)
2. 만약 T = 1 다음 (N) = O (N ^{K + 1})
3. 만약> 한 후 T (N) = O (N K *는 ^N/ b)

I는 여기에서 해결할 수 같다.

희망 하시겠습니까?