데브림의 블로그 포스팅 한 것들을 한 눈에 확인하고 싶다면 클릭!
👉 https://github.com/DevLimK1/tistory-map 👈
필자는 합병(병합) 알고리즘(merge sort)이 시간복잡도가 왜 N*logN 인지 오랜시간 이해하지 못했다.
나뿐만이 아니라, 알고리즘 시간복잡도 자체는 다들 이해하기 어려워하는 분야이기도 하고,
병합 알고리즘 시간복잡도에 관련하여 나처럼 이해하기 어려워하는 분들도 많이 있는 거 같았다...
암기보다는 이해를 해야하는 성격이라서 늘 이해하고 싶은 갈증이 있었다.
오늘 백준 알고리즘 문제를 풀다가 병합 알고리즘을 사용해서 풀어야하는 문제가 나왔고,
문제를 푼 후 '시간복잡도를 다시 이해해보자' 라는 불굴의 의지로 검색과 강의를 보면서 노력한 끝에
진짜 신기하게도 빡! 이해하기 시작하여
이 이해한 것을 잊고싶지 않기에
바로 기록에 남기고자 포스팅을 한다.
물론 이 기쁨을 나같이 오랜시간 병합알고리즘의 시간복잡도를 이해하지 못하는 분들을 위해
열심히 작성해보겠다.
여러분들도 이 포스팅을 통하여 이해가 빡! 되면 좋겠다👍
설명하기 전에 병합알고리즘이 어떤 원리로 이루어지는 알고리즘인지 알고 있다는 전제하에 설명하겠습니다.
😀 정렬되지 않은 8개의 숫자(6,7,2,3,9,5,1,4)를 병합 알고리즘을 사용하여 오름차순으로 정렬 한다고 가정하겠습니다.
N=8인 배열을 한 개의 배열이 될 때까지 2로 나누면서(N/2) 분할합니다.
😀 여기서 다르게 생각해 볼 것은, 맨 아래에 한 개씩 분할 된 것을 N=8로 다시 만들어 주려면 어떻게 해야 할까요?
위에서 2로 나눈 것과 반대로 2씩 곱해줘야 합니다.
😀 그렇다면, N=8이 되기위해서 2를 몇번 곱해야 할까요?
x를 구하기 위해서 위와 같이 2를 밑으로 하는 log로 식을 써서 구해보니 x=3이 나온 것을 알 수 있습니다.
이 말은, 2를 3번 곱해야 N=8이 된다는 것이겠죠?
(혹시 위의 계산에 대한 이해가 가지 않으시다면 log에 대한 설명은 검색해보면 많이 나온답니다😊)
😀 자, 여기가 이해하는데 가장 핵심이 되는 내용이라고 할 수 있습니다!!
N=8이 아니라 임시의 수 N이라고 한다면 2는 몇 번 곱해야 N이 될까요?
x=logN이 나온 것을 확인 할 수 있습니다.
이 말은, 2를 logN 만큼 곱해야 N이 된다는 것이죠.
무슨 말인지 아래 그림으로 확인해봅시다.
😀 맨 아래에서 N개가 되기까지 높이가 logN인 것을 확인하실 수 있겠죠?
(2를 logN만큼 곱해야 N이 된다고 위에서 확인했었죠.)
그렇다면 병합 알고리즘의 시간복잡도가 N*logN인 이유는?!
😀 위 그림이면 병합 알고리즘의 시간복잡도가 왜 NlogN인지 이해하실 수 있을 것입니다.
1개씩 분할 되었던 배열을 오름차순으로 정렬해가면서 병합하는 과정을 그린 것인데요,
변수 i,j는 병합할 때 사용하는 변수입니다.
여기서 핵심은 각 줄마다 모든 숫자 N개를 하나씩 읽어가면서 비교해서 병합한다는 것입니다.(N번 읽음)
좀 더 풀어서 설명하자면,
😀 이렇게 합쳐질 때 모든 요소 하나하나 비교해 간다는 것입니다.
설명은 여기까지 입니다.
이해하는데 도움이 많이 되셨나요??
혹시 이해가 안되는 부분 있으면 댓글 남겨주시면 바로 답글 남기겠습니다.
댓글