수정된 MergeSort 런타임 (Modified MergeSort runtime)

문제 설명

수정된 MergeSort 런타임 (Modified MergeSort runtime)

수정된 MergeSort 알고리즘의 런타임을 이해하도록 도와주세요. 고전적인 MergeSort에서 입력 배열을 두 부분으로 나누고 재귀적으로 정렬할 때 실행 시간은 다음과 같습니다. nlogn

입력 배열을 세 부분( 절반이 아님), 3분의 1마다 재귀적으로 정렬하고 마지막으로 3개의 인수로 구성된 병합 병합 하위 프로그램을 사용하여 결과를 병합합니다.

1. n
2. nlogn
3. n (로그 n) ^ 2
4. n ^ 2로그n

참조 솔루션

방법 1:

In the classic Merge Sort algorithm, there are approximately n * log2(n) comparisons and as many element copy operations, hence the time complexity of O(n.log(n)) because multiplicative constants are implicit.

If instead of splitting the array into 2 parts, you split into 3 parts, perform the same sort recursively on the parts and merge the 3 sorted slices into one, the number of comparisons increases to approximately 2 * n * log3(n) and the number of element copies is reduced to n * log3(n), but both are still proportional to n * log(n). Factoring out multiplicative constants, you still get a time complexity of O(n.log(n)).

(by richardR、chqrlie)

참조 문서

1. Modified MergeSort runtime (CC BY‑SA 2.5/3.0/4.0)