병합 정렬

그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

정렬 - 병합정렬

해결된 질문

작성

260

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

병합 정렬의 시간복잡도가 O(nlogn)인 것은 이해가 가는데, 설명해주신 부분에서 n번의 비교가 필요하다는 부분에 대해 질문 드립니다!

정렬 하려는 배열을 반으로 나눠 길이가 1인 배열을 만드는 과정에서 시간복잡도 logn이 소요된다는 것은 이해했습니다.

그런데 1 + 1 -> 2로 병합하는 과정에 2번의 비교,

2 + 2 -> 4로 병합하는 과정에서 4번의 비교가 필요하다는 부분이 이해가 잘 되지 않습니다.

최악의 경우에 1 + 1 -> 2 병합의 경우 1번 2 + 2 -> 4 병합의 경우 3번 ... 이렇게 n - 1번의 비교가 필요하다고 생각되는데 왜 n번의 비교가 되는지 궁금합니다!

algorithm

답변 1

감자

지식공유자

while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex){
  if(arr[leftAreaIndex] <= arr[rightAreaIndex]){
    tempArr[tempArrIndex] = arr[leftAreaIndex++];
  } else {
    tempArr[tempArrIndex] = arr[rightAreaIndex++];
  }
}

해당 코드를 본다면 dev.taeyeong님께서 말씀해주신대로 n-1번이 맞습니다.

하지만 실제로 이 아래 코드를 보면

if(leftAreaIndex > midIndex){
  ...
} else {
  ...
}

코드로 나머지 하나의 원소까지 비교합니다.
1+1 -> 2가 될 때는 두 번의 비교가 이루어지는 것이죠.
하지만 몇 개의 배열이 있냐에 따라서(2+2, 4+4), 그리고 어떻게 정열 되어있냐에 따라서 비교 횟수가 달라질 수 있습니다.
정확히 n, n-1, n-2라고 집어내기 힘들죠.

그러나 우리는 빅오 표기를 사용하므로 최악의 경우만 생각하고, 최악의 경우가 n-1이나 n-2이라도 상수는 제거하기 때문에 n이라고 말합니다!

궁금증이 해결되셨나요?ㅎㅎ

dev.taeyeong

질문자

넵 이해했습니다 ㅎ

좋은 강의 만들어 주셔서 감사합니다! 이제 심화편 들으러 가겠습니다!

감자

지식공유자

파이팅입니다! ㅎㅎ

인프런 커뮤니티 질문&답변

병합 정렬