(CS50)-알고리즘 기초(합병정렬)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 합병 정렬
• 분할 정복

합병 정렬

• 원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
  • 재귀적으로 구현되기에 추루 재귀를 학습하면 더 이해가 쉬워짐

실행

• (3, 5, 2, 6, 4, 1) 이라는 배열을 통해 합병정렬을 한다.

(합병정렬 의사코드)

(합병정렬예시)

• 6개의 원소를 가진 배열은 반으로 나뉘고, 원소가 1개가 될 때까지 계속 나누어지게 됨
• <합병정렬예시>의 4번째 줄 처럼 모든 원소가 1개가 되었을 때, 다시 합치면서 정렬이 이루어짐
• 4번째 줄에서 5번째 줄로 넘어가면서 3과 5의 크기를 비교하고 정렬된 채로 넘어가듯이
• 나머지 나누어진 부분도 같은 방식으로 병합
• 4번째 줄을 중심으로 나누어지고(2,3번째) 합쳐지는 과정(5,6번째 줄)이 역순임.
• 메모리의 필요 공간이 늘어나게 됨
  • 나누고 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때까지 기억하고 있어야 하기에

시간 복잡도

• O(n log n)
  • 만약 8개의 원소가 있다면 3번 나누어짐
  • n개의 원소가 있을 때 다 나눠지기까지 호출되는 함수의 개수는 log n개
  • 합쳐지는 과정에서 각 원소들의 크기를 비교하기에 n번의 비교과정이 있음
  • 즉, 한번 나눠질때마다 n번의 비교 횟수가 추가됨
• 분할정복
  • 모든 데이터를 다 보는게 아니라 절반 그리고 그 절반을 보는 방식
  • 탐색 시간이 굉장히 짧다