반복 알고리즘 (즉, 반복 없음)을 사용하여 나누기 및 접근 방법 을 사용하여 알고리즘을 만들려고 시도했지만입니다.반복 나누기 및 정복 알고리즘
루프 접근 방법에 대해 혼란 스럽습니다.
기본 케이스에 충돌 할 때까지 문제를 작은 하위 문제로 분해해야합니다. 나는 이것이 여전히 사실이라고 가정한다. 그러나 더 큰 문제를 해결하기 위해 작은 하위 문제를 어떻게 (재귀없이) 사용할 수 있을지 모르겠다.
예를 들어, 1 차원 공간에서 가장 가까운 점 쌍을 찾는 알고리즘을 고안하려고합니다. 더 높은 차원으로 내 자신을 일반화하려고하지만. L이 정수 좌표의리스트 인 ℝ 인 nearest_pair (L) 함수를 가지고 있다면, 어떻게이 문제를 해결할 수있는 ITERATIVE 알고리즘을 나눌 수 있고 정복 할 수 있을까요?
반복 알고리즘에 어떤 재귀 알고리즘을 설정하는 싼 방법 (일반성 내가 파이썬을 사용하고 손실없이)
는 재귀 기능을 루프에 넣어 자신 만의 스택을 사용하는 것입니다. 이렇게하면 함수 호출 오버 헤드가 제거되고 불필요한 데이터가 스택에 저장되지 않습니다. 그러나 이것은 일반적으로 "최상의"접근 방식이 아닙니다 ("최상의"은 문제와 상황에 달려 있습니다).당신이 문제를 말한 것처럼, 목록을 하위 목록으로 분해하고 각각의 가장 가까운 쌍을 찾은 다음 두 결과 중에서 가장 가까운 쌍을 가져옵니다. 이를 반복적으로 수행하려면 위에서 언급 한 일반적인 방법보다이 방법에 접근하는 더 좋은 방법은 다른 방법으로 시작하는 것입니다. 크기가 3 인 목록 (보고자하는 세 쌍이 있음)을보고 거기에서부터 작업하십시오. 크기 2의 목록은 사소한 것입니다.
마지막으로 좌표가 정수인 경우 Z가됩니다 (R의 훨씬 작은 부분 집합).
네 말이 맞아. 나는 Z를 의미 :-). Stack 아이디어에 대해 생각해 보았습니다. 그러나이 알고리즘을 분석하려고 시도하고 있으며 정확성을 증명하기 때문에이 아이디어를 피하고 싶습니다. 내가 무슨 뜻인지 이해하면 상향식 접근 방식을 제안하고 있습니까? – TimelordViktorious
@TimelordViktorious 예; 알고리즘 관점에서 볼 때 서로 다른 순서를 지정할 수도 있지만 반복적 인 버전은 상 향적으로 상향식입니다 (메모리에서 서로 가까이있는 요소를 작업하는 데 더 많은 시간을 소비하므로 캐시 성능이 향상되는 경향이 있음) – Andrew
이렇게하기 위해서 목록의 끝 부분에 도달 할 때까지 목록 L을 통해 선형 스캔을하고 한 번에 3 개 요소의 파티션을보아야합니다 (또는 2). 내가이 일을하는 방식에 맞습니까? – TimelordViktorious
재귀를 사용할 수없는 특별한 이유가 있습니까? – Gormador
클래스에서 주어진 과제에 대한 반복 알고리즘을 설계해야합니다. 나는 이것을 재귀 적으로 (D & C를 사용하여) 해답을 알고 있으며 이것을 반복 코드로 변환하고 D & C 접근법이 O (n^2)에 반대되는 O (nlogn) 시간에 있다는 것을 확신 할 수 있다고 확신한다. – TimelordViktorious
그것이 내가 두려워했던 것입니다. 특히 수업 과제의 맥락에서, 코드의 용어로 이미 시도한 것을 보여주기 전에 여기서 도움을 얻지는 않을 것입니다. 질문을 이해하는 것은 특히 언어가 아닌 일반적인 프로그래밍에 관한 것입니다. 아아, 당신은 어떤 시점에서 코드를 작성해야하고 이것은 구체적인 응답에 영향을 줄 것입니다 ... 누군가가 대답 한 것처럼 보입니다. 너 운이있는 것 같아! – Gormador