**알고리즘(Algorithm)**이란 명확히 정의된 문제를 해결하거나 특정 입력을 출력으로 변환하기 위한 단계적인 계산 절차를 의미합니다.
1. 알고리즘의 5가지 필수 조건
- 입력 (Input): 외부에서 제공되는 데이터가 0개 이상 존재해야 함.
- 출력 (Output): 최소 1개 이상의 결과가 명확히 발생해야 함.
- 명확성 (Definiteness): 각 단계는 모호하지 않고 명확해야 함.
- 유한성 (Finiteness): 한정된 수의 단계를 거친 후 반드시 종료되어야 함.
- 유효성 (Effectiveness): 모든 명령은 실행 가능하고 현실적이어야 함.
2. 점근적 분석과 Big-O 표기법
입력 크기 $N$이 증가함에 따라 실행 시간이나 메모리 사용량이 어떻게 변화하는지를 나타내는 분석 방법입니다.
- Big-O ($O$): 최악의 경우 (Upper Bound) - 알고리즘 상한 성능 표기.
- Big-Omega ($Omega$): 최선의 경우 (Lower Bound) - 알고리즘 하한 성능 표기.
- Big-Theta ($Theta$): 평균적/정확한 한계 (Tight Bound) - 상한과 하한이 일치할 때.
3. 대표적인 시간 복잡도 등급 비교
| 표기법 | 명칭 | 설명 및 예시 알고리즘 |
|---|---|---|
| $O(1)$ | Constant | 입력 크기와 무관하게 일정 (배열 인덱스 접근, 스택 push/pop) |
| $O(log N)$ | Logarithmic | 연산마다 탐색 범위가 절반으로 줄어듦 (이진 탐색) |
| $O(N)$ | Linear | 입력 크기에 비례 (선형 탐색, 단일 for문) |
| $O(N log N)$ | Linearithmic | 효율적인 정렬 알고리즘 (퀵 정렬, 병합 정렬, 힙 정렬) |
| $O(N^2)$ | Quadratic | 이중 반복문 (선택 정렬, 삽입 정렬, 버블 정렬) |
| $O(2^N)$ | Exponential | 재귀적 피보나치 수열 (효율적인 기법 미적용 시) |
4. 시간 복잡도 vs 공간 복잡도
- 시간 복잡도 (Time Complexity): 알고리즘을 수행하는 데 걸리는 연산 횟수의 측량.
- 공간 복잡도 (Space Complexity): 알고리즘 실행에 필요한 메모리 공간의 양 (보조 공간 포함).
최근 컴퓨팅 환경에서는 메모리 용량이 대폭 증가했기 때문에 시간 복잡도 최적화를 1순위 목표로 삼는 경우가 많습니다.
5. 자주 묻는 질문 (Q&A)
Q. 왜 알고리즘 분석 시 최악의 경우(Big-O)를 주로 사용하나요? A. 최악의 경우를 파악하면 어떠한 입력 데이터가 들어오더라도 해당 시간 이내에 완료됨을 보장(Guarantee)할 수 있어 시스템 예측 가능성이 높아지기 때문입니다.