나누기 및 정복 - 왜 작동합니까?

Question

나는 머지 소트 및 퀵 같은 알고리즘은 분할 정복 패러다임을 사용하는 것을 알고 있지만,이 시간 복잡도를 낮추는 작업 않는 이유를 궁금하네요 ...

이유는 일반적으로하지 않습니다 "분열과 정복"알고리즘을 비 분할 정복자보다 잘 작동합니까?

Answer 1

수학이 그것을 지원하기 때문에 분열과 정복이 효과가 있습니다!

몇 격차를 고려하고 알고리즘을 정복 :

1) 이진 검색 :이 알고리즘은 반마다로 입력 공간을 줄일 수 있습니다. 직선적 인 검색보다 낫다는 것이 직관적으로 분명합니다. 많은 요소를 보지 않아도됩니다.

하지만 얼마나 좋을까요? 우리는 재발 (참고 :이 최악의 경우 분석을위한 재발입니다) : 얻을

T(n) = T(n/2) + O(1)

수학 T(n) = Theta(log n) 있음을 의미한다. 따라서 이것은 선형 검색보다 기하 급수적으로 우수합니다.

2) 병합 정렬 : 여기서 우리는 두 개의 (거의 같은) 반으로 나뉘어 반을 정렬 한 다음 병합합니다. 이것이 왜 2 차보다 나은가? T(n) = Theta(n log n) 그 (마스터 정리를 사용하여 말을)

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

그것은 수학적으로 표시 할 수 있습니다 :이 재발입니다. 따라서 T (n)은 2 차보다 점근 적으로 우수하다.

는 순진 퀵 수학적으로, 그리고 최악의 경우, 차 나옵니다보다 좋은 것은 아닙니다

T(n) = T(n-1) + O(n)

로 우리에게 최악의 경우의 재발을주고 끝나는 것을 관찰 버블 정렬 (asymptotically speaking). 그러나 우리는 평균 경우에 quicksort가 O (n log n)임을 보여줄 수 있습니다.

3 선택 알고리즘 : 이것은 k 번째로 큰 요소를 찾기 위해 정복 알고리즘을 나눕니다. 이 알고리즘이 정렬 (또는 심지어 2 차가 아니라)보다 낫지는 전혀 분명하지 않습니다.

그러나 수학적으로는 재발 (다시 최악의 경우)

T(n) = T(n/5) + T(7n/10 + 6) + O(n)

그것은 수학적으로 그 T(n) = O(n)를 표시 할 수 있습니다 나옵니다 및 따라서 정렬보다 낫다. 아마도

일반적인 방법들을 살펴합니다 :

당신이 각 하위 문제는 현재의 하위 트리가되고 노드가 작업의 양을 태그 할 수있는 나무와 같은 알고리즘을 볼 수 있습니다 완료되면 전체 작업을 각 노드에 추가 할 수 있습니다.

이진 검색의 경우 작업은 O (1) (그냥 비교)이고 하위 트리 중 하나는 작업이 0이므로 총 작업량은 O (log n) (본질적으로 경로 우리가 이진 검색 트리에서하는 것처럼).

병합 정렬의 경우 k 개의 하위 노드가있는 경우 작업은 O (k) (병합 단계)입니다. 각 레벨에서 수행되는 작업은 O (n) (n, n/2 + n/2, n/4 + n/4 + n/4 + n/4 등)이며 O 병합 정렬은 O (n log n)입니다.

최악의 경우, 이진 트리는 실제로 링크 된 목록이므로 작업은 n + n-1 + ... + 1 = Omega (n^2)입니다.

선택 정렬의 경우 시각화하는 방법을 알지 못하지만 3 명의 어린이 (n/5, 7n/10 및 나머지)가있는 트리를 보는 것이 도움이 될 것이라고 생각합니다.

Answer 2

분할 및 정복 알고리즘은 "보통 더 잘 작동하지 않습니다". 다른 분단 및 정복 알고리즘과 마찬가지로 작동합니다. 그들은 정렬 복잡도를 낮추지 않고 다른 알고리즘만큼 훌륭하게 수행합니다.

Answer 3

분할 및 정복 알고리즘은 작업량이 적기 때문에 빠르게 작동합니다.

바이너리 검색의 고전적인 divide-and-conquer 알고리즘을 고려하십시오. 답변을 찾기 위해 N 항목을 보는 대신 이진 검색은 Log2N 개만 확인합니다. 당연히, 당신이 더 적은 일을 할 때, 당신은 더 빨리 끝낼 수 있습니다; 그것은 정확하게 분할 - 및 - 정복 알고리즘에서 진행되고 있습니다.

물론 결과는 작업을 나누는 데있어 전략이 얼마나 좋은가에 따라 달라집니다. 즉, 모든 단계에서 나누기가 공정한 경우 (즉, 작업을 반으로 나누는 경우) 완벽한 Log2N 속도가 발생합니다. 그러나 나누기가 완벽하지 않은 경우 (예 : 퀵 정렬의 최악의 경우, O(n^2)은 각 반복마다 하나의 요소 만 제거하기 때문에 배열을 정렬하는 경우) 알고리즘이 수행하는 것처럼 분할 및 정복 전략은 도움이되지 않습니다 일의 양을 줄이지 말라.

Answer 4

어떤 경우에는 문제를 원래의 문제보다 훨씬 더 작은 하위 문제로 나누는 것이 더 낫습니다. 심지어 부분 솔루션을 결합 (병합)하는 복잡성을 추가 할 때도 마찬가지입니다.

나는 전쟁 (적을 제거하는 것)에 대한 실제적인 비유가 정확하다고 생각합니다. 같은 시간에 두 가지를 다룰 때보 다 적을 분리하여 분리하는 것이 일반적으로 더 좋습니다.

alestanis가 이미 언급했듯이 divide and conquer 알고리즘은 단지 알고리즘의 한 클래스에 불과하므로 분수 나 정복보다 빠르다고 보장 할 수는 없습니다. 예를 들어 힙 정렬은 병합 정렬과 동일한 점근 복잡성을가집니다. 반면에 Quicksort는 그 둘 모두보다 더 복잡합니다. 그러나 평균적으로는 더 좋은 결과를냅니다 ....