merge sort의 실행 시간 :: 모든 요소가 동일 함

Question

모든 요소가 동일한 크기 n의 배열이 있다고 가정합니다. O (n)은 무엇입니까? 선형일까요?

Answer 1

이것은 알고리즘 구현 방법에 따라 다릅니다.

mergesort의 표준 "바닐라"구현을 사용하면 배열을 정렬하는 데 필요한 시간은 각 단계에서 필요한 병합마다 선형 시간이 걸리기 때문에 항상 Θ (n log n)이됩니다.

그러나 적절한 최적화를 통해 시간 O (n)에서 실행되도록 할 수 있습니다. 많은 mergesort 구현에서는 입력 배열이 지속적으로 수정되어 더 큰 범위와 큰 범위가 정렬되고 병합 단계가 발생하면 알고리즘은 외부 버퍼를 사용하여 두 개의 인접한 정렬 된 범위를 병합합니다. 이 경우, 할 수있는 멋진 최적화가 있습니다 : 병합하기 전에 첫 번째 범위의 마지막 요소가 두 번째 범위의 첫 번째 요소보다 작거나 같은지 확인하십시오. 그렇다면 병합 된 두 범위가 이미 정렬되어 있으므로 병합을 수행 할 필요가 없습니다.

이 최적화를 수행하고 모든 요소가 이미 정렬 된 배열을 정렬한다고 가정 해 보겠습니다. 무슨 일이야? 음, mergesort를 호출 할 때마다 두 가지 더 많은 재귀 호출이 실행됩니다. 반환 된 후에는 정렬 된 범위의 끝점을 확인할 수 있으며 이미 정렬 된 순서로되어 있으므로 더 이상 작업 할 필요가 없습니다. 전반적으로, 이는 호출 당 O (1) 작업을 수행하고 있으므로, 알고리즘의 시간 복잡도이 점화식 가지고

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

을

이것은 O (n)으로 풀리므로 선형 작업 만 수행됩니다.