알고리즘 성능 분석 시, 입력 크기(n)에 대한 실행시간 및 공간(메모리) 사용량 표기법
→ n이 커질 때 얼마나 cost가 증가하는지 수학적으로 표현하는 개념
왜 필요?
- HW 특성이나 구현 방식과 독립적으로 알고리즘 성능 분석
- n 관계식, Worst, Mean, Best Case에 대한 수학적 분석
종류
-
Big-O
- Worst case 실행시간의 상한을 나타냄
- n이 매우 클 때 성능 분석하는 가장 흔한 방법
- 가장 빠르게 증가하는 항만 고려하고, 상수는 무시 (n이 클수록 유효할 듯)
표기 예시 description O(1) 상수 시간 입력 크기(n)와 무관하게 항상 일정한 실행 시간 O(log n) Log 시간 이진 탐색 (Binary Search) O(n) 선형 시간 단순 반복문 (for loop) O(n log n) 로그 선형 시간 Quick Sort, Merge Sort O(n^2) 제곱 시간 이중 루프 (Bubble Sort, Selection Sort) O(2^n) 지수 시간 Fibonacci Recursive -
예제
Binary Search란 배열에서 특정 값을 찾는 알고리즘으로, 매번 검색 범위를 절반으로 줄이면서 탐색하는 방식으로 시간 복잡도는 O(log n)이다.
→ 배열이 오름차순 등으로 정렬되어 있어야겠네?
-
Big-Ω 표기법 ; Omega
- Best case의 하한 시간 → 최소한 이 정도의 성능을 갖는다
표기 예시 description Ω(1) Linear Search 목표 값이 첫 번째 위치에 있을 때 Ω(n log n) Quick Sort 이상적인 pivot 선택이 된 경우 -
Big Θ 표기법 ; theta
- Best와 worst의 경우가 같을 때 → 알고리즘의 정확한 실행 시간 경계를 나타냄
- n이 커질 때 알고리즘 성능이 Big O와 Big Ω 일치할 때 사용
표기 예시 description Θ(n^2) Bubble Sort 최악과 최상이 모두 O(n^2) Θ(n) Linear Search 항상 n번 비교하므로 (loop문) -
Quick Sort 개념 추가
- 평균 시간 복잡도는 O(n log n), 최악의 경우 = pivot이 항상 최소/최대값일 때 > O(n^2)
- 동작 원리
- Divide: 배열에서 원소(pivot) 선택(첫 번째 마지막, 중간 or 랜덤)하고 대소 비교하여 나눔 →partitioning
- Conquer: 왼쪽 부분과 오른쪽 부분을 각각 다시 Quick Sort (재귀 호출)
- Combine: 전체 정렬 완료
- 일반적으로 빠르고 in-place 정렬해서 메모리 적게 씀
- Stable Sorting이 아니고(최악의 경우 n^2), 재귀 호출로 Stack-overflow 위험 존
