알고리즘 3 판 소개에서 다중 스레드 병합 정렬 읽기 중이었습니다. 그러나 나는 다음 병합-정렬 너 한테 필요한 프로세서의 수와 혼란 스러워요 :병합 정렬을위한 PRAM (병렬) 알고리즘
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 spawn MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 sync
6 MERGE(A, p, q, r)
병합 표준 병합 알고리즘이다. 이제이 알고리즘에 필요한 프로세서의 수는 얼마입니까 ?? 비록 그것이 O (N)이어야한다고 가정하고 있지만 책은 O (log n)라고 주장하고 있습니다, 왜? 참고 MERGE 프로 시저를 다중 스레드하지 않습니다. 예를 들어 설명하는 것이 도움이 될 것입니다. 미리 감사드립니다.
O (log n) 값은 "필수"알고리즘을 실행하는 데 필요한 CPU 수는 아니지만 알고리즘에 의해 실제로 구현 된 "병렬 처리"입니다. MERGE 자체는 병렬 처리되지 않으므로 모든 프로세서를 사용할 수있는 경우에도 O (n) 프로세서가 있으면 모든 이점을 얻을 수 없습니다.
즉 병합 정렬의 단일 스레드 직렬 시간 복잡성은 O (n log n)입니다. 병합 비용으로 'n'을 생각할 수 있으며 병합을 재귀 호출하여 병합 할 수있는 단계로 배열을 가져 오는 요소로 'log n'을 고려할 수 있습니다. 재귀를 병렬 처리하지만 병합이 여전히 직렬 인 경우 O (log n) 인수는 저장하지만 O (n) 인수는 그대로 유지됩니다. 따라서 병렬 처리는 사용 가능한 프로세서가 충분하지만 O (n)에 도달 할 수없는 경우 O (log n)의 순서가됩니다.
다른 말로하면 O (n) CPU를 사용할 수 있더라도 대용량 MERGE가 발생하기 시작할 때 대부분의 CPU가 매우 빨리 유휴 상태가되고 CPU가 더 적게 작동합니다.
나는 O (log n)가 평행법이라는 것을 이해했다. 그러나 책에서이 알 고를 설명 한 후에,이 알고리즘은 선 속도를 달성 할 것이고 이것이 선형 속도를 달성한다면 정의에서 Tp = O (n)와 같이 프로세서의 수를 O (log n)로 정의했다. optiaml을 작동하십시오. 나중에이 책은 병렬 처리가 O (n/(log n)^2) 인 곳에서 Tp = O ((log n)^3)을 가진 알고리즘을 소개했다. 하지만 내 질문은 병렬성에 관한 것이 아닙니다! –
O (lg3 n) 알고리즘은 MERGE도 병렬 처리하는 알고리즘입니다. 하지만 당신은 그 질문에 스스로 대답했습니다. 병렬 처리로 만 O (log n) 요소를 제거 할 수 있기 때문에 병렬 병합없이 O (log n) 병렬 실행 = CPU를 사용하면 최대 이점을 얻을 수 있습니다. –
음 재귀 깊이가 있으므로 우리는 Tp = O (n) 시간에 해결하기 위해 O (log n) 개의 프로세서 만 사용합니다. 따라서 p * Tp = O (n log n). 고마워요. –