병합정렬
-
병합 정렬알고리즘/정렬 2021. 12. 25. 00:18
병합 정렬: 모든 원소들이 하나로 남을때까지 정확하게 절반으로 나눈 후 나중에 합쳐서 정렬하는 알고리즘. Ex) (이미 하나까지 전부 반으로 쪼게진 상태라 가정하고 2의 배수만큼 차례대로 합쳐진다.) 7 6 5 8 3 5 9 1 67 58 35 19 5678 1359 13556789 시간 복잡도: O(N*log N) 너비가 n이고 높이가 log n (정렬이 되어있는 상태에서 데이터를 하나씩 읽어나가 새롭게 정렬을 하므로 n * log n에 비례.) 병합 정렬의 경우 항상 정확히 절반으로 분할되고 정복하는 과정이 반복되므로 최악의 경우에도 O(N*log N)을 보장한다. (퀵 정렬은 편향되게 분할 할 가능성이 있으므로 최악의 경우 O(N^2)) 단점: 기존의 데이터를 담을 추가적인 배열 공간이 필요하여 메..