합병정렬의 시간 복잡도가 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를 합치는데 '누가더 크냐?' 한번만 하면 되는거 아닌가요ㅑ?? ㅠㅠ 오밤중에 공부하다가 질문드립니다.
shoomj 8달 전
합병정렬의 시간 복잡도가 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를 합치는데 '누가더 크냐?' 한번만 하면 되는거 아닌가요ㅑ??
ㅠㅠ 오밤중에 공부하다가 질문드립니다.