알고리즘을 배운다는 것은 단순히 "정렬하는 법"을 외우는 것이 아니다. 핵심은 왜 이 알고리즘이 올바른지, 그리고 얼마나 빠른지를 분석하는 능력을 기르는 데 있다. 이 글에서는 가장 기본적인 정렬 알고리즘인 Insertion Sort와 Merge Sort를 통해 알고리즘 분석의 기초 개념을 정리한다.
Insertion Sort (삽입 정렬)
Insertion Sort는 카드 게임에서 손패를 정리하는 방식과 같다. 새 카드를 받으면, 이미 정렬된 카드들 사이에서 올바른 위치를 찾아 끼워넣는다.
배열 A[1..n]에서 A[1..j-1]까지 이미 정렬된 부분 배열에 A[j]를 삽입하는 과정을 반복한다. 이처럼 정렬된 영역을 하나씩 확장해 나가는 방식을 점진적 접근법(Incremental Approach) 이라 한다.
이와 대비되는 접근법이 분할 정복(Divide and Conquer) 으로, 뒤에서 다룰 Merge Sort가 대표적이다.
알고리즘 분석: 무엇을 검증하는가?
알고리즘을 분석할 때 확인하는 두 가지 핵심 질문이 있다.
- 정확성(Correctness): 이 알고리즘이 항상 올바른 결과를 내는가?
- 효율성(Efficiency): 얼마나 빠르게 동작하는가? (시간 복잡도)
정확성 증명: 루프 불변식 (Loop Invariant)
알고리즘의 정확성을 증명하는 대표적인 기법이 루프 불변식(Loop Invariant) 이다. 수학적 귀납법과 유사한 구조를 가진다.
루프 불변식이란?
for 루프의 각 반복이 시작될 때, 부분 배열 A[1..j-1]은 원래 A[1..j-1]에 있던 원소들로 구성되되, 정렬된 상태를 유지한다.
즉, 원소가 추가되거나 사라지지 않고, 순서만 바뀐다는 것이 핵심이다.
이를 세 단계로 증명한다.
1. 초기 조건 (Initialization)
j=2일 때, A[1..j-1]은 원소가 하나뿐인 A[1]이다. 원소가 하나이므로 자명하게 정렬되어 있다.
2. 유지 조건 (Maintenance)
외부 for 루프의 본문은 A[j-1], A[j-2], A[j-3], ... 를 한 칸씩 오른쪽으로 이동시키며, A[j]가 들어갈 적절한 위치를 찾는다. 이 과정을 거치면 A[1..j]가 정렬된 상태가 되므로, 다음 반복에서도 불변식이 성립한다.
3. 종료 조건 (Termination)
외부 for 루프가 j = n+1에서 종료된다. 불변식에 따라 A[1..n]은 원래 원소들이 정렬된 상태로 구성된다. 즉, 전체 배열이 정렬되었음이 증명된다.
효율성 분석의 기초
알고리즘의 효율성은 주로 시간(Time) 을 기준으로 측정한다. 저장 공간(Storage)도 고려 대상이지만, 보통 시간이 더 중요하다.
RAM 모델 (Random-Access Machine)
알고리즘 분석에는 RAM 모델이라는 이론적 컴퓨터 모델을 사용한다.
- 명령어가 하나씩 순차적으로 실행된다 (동시 실행 없음)
- 각 명령어는 상수 시간이 소요된다 (산술, 데이터 이동, 제어 연산)
- 데이터 타입은 정수, 부동소수점
- 메모리 계층이 없다 (캐시나 가상 메모리 없음)
실제 컴퓨터와는 다르지만, 알고리즘 간의 상대적 성능 비교에 충분히 유효한 모델이다.
입력 크기 (Input Size)
알고리즘의 수행 시간은 입력 크기에 따라 달라진다. 입력 크기의 정의는 문제에 따라 다르다.
- 정렬 문제: 원소의 개수 n
- 그래프 알고리즘: 정점(Vertex)과 간선(Edge)의 수
수행 시간 (Running Time)
수행 시간은 실행되는 기본 연산(primitive operation)의 횟수로 정의한다. 기본 연산은 기계에 독립적(machine-independent) 으로 정의되며, 의사코드의 각 줄은 상수 시간이 걸리되 줄마다 다른 상수가 적용된다.
시간 복잡도 분석의 세 가지 관점
- 최악의 경우(Worst-case): 가장 일반적으로 사용되며, 수행 시간의 상한(upper bound) 을 제공한다
- 평균적인 경우(Average-case): 입력의 통계적 분포에 대한 가정이 필요하다. 때때로 사용된다
- 최선의 경우(Best-case): 실질적 의미가 거의 없다. 특정 입력에 맞춰 "치팅"이 가능하기 때문이다
Insertion Sort의 시간 복잡도
위 분석에서 볼 수 있듯이, Insertion Sort의 시간 복잡도는 입력 상태에 따라 크게 달라진다.
- 최선의 경우 (이미 정렬된 배열):
- 최악의 경우 (역순으로 정렬된 배열):
Merge Sort의 시간 복잡도
Merge Sort는 분할 정복(Divide and Conquer) 패러다임을 따른다. 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 뒤, 두 정렬된 배열을 합치는 방식이다.
점화식을 이용한 분석
Merge Sort의 시간 복잡도는 점화식(Recurrence Equation)으로 표현된다. 마스터 정리(Master Theorem)를 적용하면 이다.
Insertion Sort의 과 비교하면, 입력 크기가 작을 때는 Insertion Sort가 더 빠를 수 있다. 하지만 입력이 충분히 크다면, Merge Sort가 항상 더 빠르다.
재귀 트리를 이용한 분석
재귀 트리(Recursion Tree)를 그려보면, 각 레벨에서의 비용 합이 이고 트리의 높이가 이므로, 전체 비용이 임을 직관적으로 확인할 수 있다.
연습 문제
1. 메모이제이션 피보나치의 공간 복잡도
메모이제이션(Memoized DP)을 적용한 fibo(n)의 공간 복잡도는 이다.
그 이유는 두 가지다.
- 배열 크기: 메모이제이션 테이블이 n개의 값을 저장하므로
- 호출 스택: 재귀 호출이 최대 n번 중첩되므로 스택 공간도
두 요소 모두 이므로, 전체 공간 복잡도는 이다.
2. 다양한 정렬 알고리즘의 시간 복잡도
Selection Sort (선택 정렬)
시간 복잡도는 이며, Best case와 Worst case가 동일하다. 매번 전체 남은 배열에서 최솟값을 찾아야 하기 때문이다.
Bubble Sort (버블 정렬)
시간 복잡도는 이며, 역시 Best case와 Worst case가 동일하다.
Insertion Sort (삽입 정렬)
- Best case: -- 이미 정렬된 경우
- Worst case: -- 역순 정렬된 경우
Selection Sort, Bubble Sort와 달리 최선/최악이 다르다는 점이 특징이다.
Quick Sort (퀵 정렬)
Quick Sort에서 Partition은 리스트를 분할하고 pivot을 기준으로 작은 원소와 큰 원소를 나누는 과정이다.
Worst case -- pivot이 항상 최솟값 또는 최댓값인 경우:
결과:
Best case -- pivot이 항상 중앙값인 경우:
결과:
3. Binary Search (이진 탐색)
Binary Search의 시간 복잡도는 이다.
그렇다면 Insertion Sort에서 삽입 위치를 찾을 때 이진 탐색을 사용하면 전체가 이 될까?
정답은 아니다. 삽입 위치를 이진 탐색으로 에 찾을 수는 있지만, 그 위치에 원소를 삽입하려면 뒤의 원소들을 한 칸씩 밀어야 한다. 이 이동 작업이 여전히 이므로, 전체 시간 복잡도는 에서 변하지 않는다.
HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.