shoomj   1달 전

합병정렬의 시간 복잡도가 n log n 일고 알고 있는데요.
log n 은 한번에 이해가 가는데, n이 이해가 안되네요.
책에는 예를 들어 크기가 8인 배열을 합병정렬하는데, 이걸 가장 작은 단계 그러니까
배열에 1개의 원소만 들어간 가장 작은 상황에서 두 배열을 합칠 때 최대 2개의 연산이 필요하고 4쌍이므로 2 * 8해서
최대 8번이 발생하고
배열 크기 2인 배열들 합칠 때는 최대 4번씩 * 2 해서 8번이고 ,....
해서 merge가 n복잡도 나온다는데, 전혀 이해가 안갑니다.
배열에 1개의 원소만 들어간 상황에서 크기가 1인 부분 배열 2개를 합병하는데 왜 최대 2개의 비교 연산이 필요한거죠? a 랑 b를 합치는데 '누가더 크냐?' 한번만 하면 되는거 아닌가요ㅑ??
ㅠㅠ 오밤중에 공부하다가 질문드립니다.

amugeona   1달 전

합병정렬의 Divide 단계에서 분할되는 깊이가 logN에 비례합니다.

각 깊이별로 Divide가 수행되어 합병해야되는 배열의 수는 많아지지만, 총 원소의 수는 똑같습니다. (N개)

따라서 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)이 됩니다.

이것을 모든 깊이에 대해(logN개만큼) 수행하기 때문에 시간복잡도는 O(N * logN)이 됩니다.

댓글을 작성하려면 로그인해야 합니다.