일정 시간 내에 작동하는 분열 및 정복?

Question

일정 시간에 실행되는 분할 및 정복 알고리즘의 예를 나에게 지적 해 줄 수 있습니까? 나는 "OMG!"과 같은 그런 종류의 상황을 생각할 수 없다. 제발 좀 가르쳐주세요. 감사합니다

나는 다음과 같은 재원을 따르는 alg : T(n) = 2T(n/2) + n은 merge sort이 될 것이라고 알고 있습니다. 문제를 2 개의 하위 문제로 나눕니다. 각 문제는 크기 n/2입니다. 그런 다음 모든 것을 하나의 정렬 된 배열로 다시 정복하기 위해 n 시간을 할애하고 있습니다.

또한 T(n) = T(n/2) + 1은 binary search이 될 것입니다.

그러나 일정한 시간에 실행하는 분할 정복 알고리즘의 T(n) = 1?

Answer 1

것입니다, 그것은 모든 입력에 대한 작업의 고정 된 금액보다 더 이상하지 않는다 할 필요가있다. 따라서 호출 수가 제한되지 않은 경우 수행되는 총 작업 수가 상수가 아니므로 모든 입력에 대해 최대 개수의 재귀 호출을 만들 수 있습니다. 또한 모든 재귀 호출에서 일정한 작업을 수행해야합니다.

기본적으로 합리적인 재발 관계를 제거합니다. 형태의 건

T (N) = (AT N/b) + O (N ^K) 재귀 호출의 수는 증가하기 때문

는 즉시 밖으로 질문 입력 n의 함수로서.

일정한 시간에 실행되는 고도로 고안된 Divide-and-Conquer 알고리즘을 만들 수 있습니다. 예를 들어 다음과 같은 문제를 고려하십시오.

입력 배열의 첫 번째 요소를 반환합니다.

이 기술적으로 한 소자 어레이의 첫 번째 요소는 그 자체와 동일

• 것을주의하여 분할 정복 해결 될 수있다.
• n 요소 배열의 첫 번째 요소는 바로 첫 번째 요소의 하위 배열의 첫 번째 요소입니다.

재발 후

T (N)이다 = T (1) + O (1)

T (1) = 1

하면 알 수 있듯이 , 이것은 매우 이상한 재발이지만, 효과가 있습니다.

나는 이런 일이 실제로 생기는 것을 들어 본 적이 없지만, 무엇이든 생각하면 나는이 대답을 세부 사항으로 업데이트하려고 노력할 것이다. (참고 :이 답변을 업데이트 할 것으로 기대하지 않습니다.^_ ^)

희망이 있습니다.