가이드라인
실습
병합 정렬 구현 방법
1. 분할: 원래의 리스트를 가능한 한 균등한 두 부분으로 나눕니다.
분할 예시
mid = len(arr) // 2 L = arr[:mid] R = arr[mid:]
2. 재귀적 정렬: 각 부분을 재귀적으로 정렬합니다.
재귀적 정렬 예시
merge_sort(L) merge_sort(R)
3. 병합: 정렬된 두 부분을 하나의 정렬된 리스트로 병합합니다.
병합 예시
i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1
시간 복잡도
-
최악의 경우 시간 복잡도
: O(nlog n)- 병합 정렬은 분할과 병합 과정에서 일정한 시간 복잡도를 유지합니다. 각 단계에서 배열을 반으로 나누고, 각 레벨에서 (n)의 작업을 수행합니다. 따라서, ( \log n ) 단계에서 총 ( n ) 작업을 수행하게 됩니다.
-
최선의 경우 시간 복잡도
: O(nlog n)- 병합 정렬은 최선의 경우에도 배열을 나누고 병합하는 과정이 동일하게 진행되므로 시간 복잡도는 변하지 않습니다.
-
평균 시간 복잡도
: O(nlog n)- 일반적인 경우에도 병합 정렬은 일정한 (O(n log n))의 시간 복잡도를 유지합니다. 배열의 초기 정렬 상태에 관계없이 동일한 작업 수행량이 필요합니다.
가이드라인
AI 튜터
배포
디자인
업로드
수업 노트
즐겨찾기
도움말