가지치기 및 검색
Prune and search가지치기 및 검색은 1983년 님로드 메기도가 제시한 최적화 문제를 해결하는 방법이다.[1]
방법의 기본이념은 각 단계에서 입력 크기가 일정한 요인 0 < p < 1. 감소와 정복 알고리즘의 형태로서, 각 단계에서 감소는 일정한 요인에 의해 감소("철거")되는 재귀적 절차다.n을 입력 크기로 하고, T(n)를 전체 가지치기 및 검색 알고리즘의 시간 복잡성으로 하고, S(n)를 가지치기 단계의 시간 복잡성으로 한다.T(n)는 다음과 같은 반복 관계를 준수한다.
이는 이진 검색의 반복과 유사하지만, 이진 검색의 상수 용어보다 큰 S(n) 용어를 가지고 있다.제거 및 검색 알고리즘에서 S(n)는 일반적으로 최소 선형(전체 입력을 처리해야 함)이다.이러한 가정으로, 재발은 해결책 T(n) = O(S)를 갖는다.이는 분할 및 교환 재발을 위한 마스터 정리를 적용하거나 재귀 하위 문제에 대한 시간이 기하 계열에서 감소하는 것을 관찰함으로써 볼 수 있다.
특히 메가도 자신은 치수가 고정되어[2] 있을 때의 선형 프로그래밍 문제와 공간의 점 집합에 대한 최소 포위구 문제에 대해 선형 시간 알고리즘에서 이 접근법을 사용했다.[1]
