1. 병합정렬
병합정렬은 3단계로 이루어져있습니다.
- 왼쪽 정렬
- 오른쪽 정렬
- 하나의 배열로 합치기 (병합)
병합은 왼쪽과 오른쪽 배열 각각 가장 작은 값을 꺼내
작은 값끼리 비교하여 정렬한 후 이와 동일한 방식으로 왼쪽과 오른쪽 배열 전부를 merge하는 과정을 말합니다.
즉 두 배열에서 작은 값 꺼내서 그 둘을 비교하는 것입니다.
만약 8개를 정렬한다면
크기가 1인 정렬되 배열 8개를 만들고
크기가 2인 정렬되 배열 4개를 만들고
크기가 4인 정렬되 배열 2개를 만들고
크기가 8인 정렬되 배열 1개를 만들어 정렬을 끝냅니다.
이처럼 1/2씩 나누는 것은 높이가 log n입니다.
여기서 n 개의 숫자를 다시 합쳐야하므로 시간복잡도는 O(nlogn)입니다.
최선의 경우 (오메가) 또한 Ω(n log n) 입니다.
빨라졌지만 여전히 최선의 경우 시간낭비를 합니다.
+) 세타
어떤 알고리즘의 상한선과 하한선이 같을 때 사용합니다.
예를 들어 selection sort는 세타(n^2)이고
병합정렬은 세타(nlogn)입니다.
2. 퀴즈 -!
1) 알고리즘의 성능 복잡도를 표현하는 표기법 중 하나로, 최악의 경우(상한)을 나타내는 것은 ?
O() // 빅오
2) 새로운 자료형을 구조체로 정의하려고 할때 필요한 코드는 ?
typedef struct
3) 전화번호부에서 선형검색으로 이펭수를 찾으면 Big-O는?
O(n)
4) 5 6 7 3 2 가 주어졌을 때 버블정렬를 한번 수행하면?
버블정렬은 2개를 서로 비교하며 큰 수가 오른쪽으로 떠오르는 정렬이므로
5 6 3 2 7이 된다.
5) 5 6 7 3 2을 선택정렬을 한번 수행하면 ?
선택정렬은 돌면서 가장 작은 수를 선택하여 왼쪽으로 옮겨놓는다.
그리고 최소값과 맨 앞 원소를 교환한다.
즉 2 6 7 3 5이 된다.
6) 선택정렬, 버블정렬, 선형검색, 이진검색을 실행시간(하한)이 빠른대로 나열하시오. 하한이 같은 경우 상한이 빠른순으로 나열
이진검색은 logn이 가장 빠를 것이고
선형검색이 하한이 n으로 다음으로 빠를것이고
선택과 버블 둘다 상한은 동일하게 O(n^2)이다.
그리고 버블은 움직임이 없을 때 멈출경우 더 빠르다.
즉 이진 - 선형 - 버블 - 선택 이다.
7) #으로 피라미드를 쌓을 때 함수 안에서 자기 자신을 호출하는 방식을 뭐라고 할까요?
재귀
8) 피라미드를 쌓는 코드에서 h가 3으로 입력되었을 때 draw은 몇번 호출될까요? 최초 호출은 제외
draw(2)
draw(1)
draw(0) 이 호출되므로 3번
9) 병합, 선택, 버블의 하한을 정렬한것은 ?
먼저 병합이 nlogn으로 가장 빠르고
6번에서 보았다시피 버블이 선택보다 하한이 빠르다.
버블의 하한은 오메가(n)이라고 한다.
즉,버블 - 병합 - 선택
10) Big - o 표기법 중 빠른 순서대로 올바르게 정렬한 것은 ?
O(1) -> O(log n) -> O(n) -> O(n^2)
중간에 선택정렬이 swap되는 걸 몰랐고 버블의 하한은 오메가(n)인지 몰라서 틀렸다.
다시 풀고 50점을 받을 수 있었다.
