-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
병합 정렬
22.12.30 23:48 작성 조회수 215
1
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 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번의 비교가 되는지 궁금합니다!
답변을 작성해보세요.
1
감자
지식공유자2022.12.31
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이라고 말합니다!
궁금증이 해결되셨나요?ㅎㅎ
답변 1