[알고리즘과 자료구조] 07. 삽입 정렬과 합병 정렬 및 재귀적 알고리즘의 복잡도
내용 정리
오늘은 Insertion Sort와 merge sort에 대해 배웠다.
필기 먼저 봅시다.
우리가 algorithm을 배울 때 Sorting문제를 많이 배우는 이유는
sorting problem이 다양한 algorithm 접근법을 제시하는 간단한 예제이기 때문이다.
Insertion Sort는 이름과 같이 새로운 element를 삽입하며 정렬하는 알고리즘인데,
우리 수업에서 두 가지 구현 방법을 배웠다.
아참 여기서 하나의 element는 정렬된 상태라고 가정한다.
첫번째는 새로운 element를 앞의 list의 변수 하나하나와 비교하여 swap한다.
이렇게 하면 코드에서 알 수 있듯이 복잡도가 O(n^2)으로 복잡하다.
두번째는 보다 효율적으로 변수를 사용하여 shift시키다가 적절한 위치에 insertion하는 것이다.
코드를 보면 복잡도가 O(n)인 것을 알 수 있다.
7주차 수강 후기
8주차가 중간평가로, 벌써 반정도 공부했다.
공부할 때마다 귀찮아서 몸부림친 것치고는 은근 빨리 온 것 같기도 하다.
8주차 수강 후기
8주차는 중간평가다. 내용이 없어 7주차에 함께 쓰려고 한다.
간단한 퀴즈 10문제가 있어서 그것만 풀면 된다.
난이도는 쉽지만 헷갈릴만한 요소가 있는 정도?
나는 두 문제를 틀렸는데, 틀린 문제만 한 번 다시 보자.
문제 3번은 포레스트와 트리의 문제다.
사실 포레스트가 뭐였는지 기억이 안났다.
8번은 재귀 알고리즘의 복잡도를 묻는 것인데 우리가 배운 재귀 알고리즘은 merge algorithm뿐이다.
merge algorithm의 복잡도는 recursion tree방법으로 O(NlgN)임을 배웠다.
하지만 답은 O(2^N).
생각해보면 당연히 N이 늘어날수록 2가 곱해지기 때문에 당연한데 괜히 merge algorithm때문에 헷갈렸다.
조심해야겠다.