기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 알고리즘 복잡도

Algorithm · 한장정리

[기술사토픽] 알고리즘 복잡도 완벽 정리 - O-Notation 한장정리

시간복잡도·공간복잡도·점근표기법(빅오/빅오메가/빅세타)을 체계적으로 정리한 기술사 핵심 학습노트

O-Notation시간복잡도공간복잡도빅오표기법빅오메가빅세타점근표기법알고리즘복잡도정보관리기술사알고리즘

Ⅰ.O-Notation 개요

알고리즘 복잡도(Algorithm Complexity)란 알고리즘이 문제를 해결하는 데 필요한 시간과 공간 자원의 양을 수학적으로 표현한 척도이다. 입력 크기 n이 증가함에 따라 자원 사용량이 어떻게 변화하는지를 점근표기법(Asymptotic Notation)으로 나타낸다.

정의

복잡도 분석은 알고리즘의 효율성을 입력 크기 n에 대한 함수로 표현하며, 하드웨어나 언어에 무관한 객관적 비교 기준을 제공한다.

구분	설명	예시
시간복잡도	알고리즘 수행에 필요한 연산 횟수	반복문 실행 횟수
공간복잡도	알고리즘 수행에 필요한 메모리 양	배열 크기, 재귀 스택
최선(Best)	가장 유리한 입력에서의 복잡도	이미 정렬된 배열
평균(Average)	모든 가능한 입력에 대한 평균	임의 배열 탐색
최악(Worst)	가장 불리한 입력에서의 복잡도	역순 정렬 배열

Ⅱ.복잡도 유형별 상세 (O(1) ~ O(n!))

빅오(Big-O) 표기법은 알고리즘의 최악의 경우 실행 시간의 상한(Upper Bound)을 나타낸다. 입력 크기 n이 커질수록 가장 빠르게 증가하는 항만 남기고 상수 계수는 무시한다.

표기	명칭	증가율	대표 알고리즘
O(1)	상수	입력 크기 무관	배열 인덱스 접근, 해시 탐색
O(log n)	로그	매우 느림	이진 탐색, AVL 트리 탐색
O(n)	선형	비례 증가	선형 탐색, 단순 순회
O(n log n)	선형로그	n보다 조금 빠름	퀵정렬(평균), 합병정렬
O(n²)	이차	빠른 증가	버블·선택·삽입 정렬
O(n³)	삼차	매우 빠름	플로이드-워셜 알고리즘
O(2ⁿ)	지수	폭발적 증가	부분집합 열거, 피보나치(재귀)
O(n!)	팩토리얼	극단적 증가	순열 생성, 외판원 문제(완전탐색)

시험 포인트

복잡도 크기 순서: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) — 이 순서는 반드시 암기. 실용적 알고리즘 설계 목표는 O(n log n) 이하 유지이다.

Ⅲ.표기법 비교 (빅오 / 빅오메가 / 빅세타)

점근표기법에는 상한·하한·상하한을 나타내는 세 가지 종류가 있으며, 각각 다른 분석 관점을 제공한다.

표기법	기호	의미	경계	사용 목적
빅오(Big-O)	O(f(n))	상한(Upper Bound)	최악의 경우	최악 성능 보장
빅오메가(Big-Ω)	Ω(f(n))	하한(Lower Bound)	최선의 경우	최선 성능 표현
빅세타(Big-Θ)	Θ(f(n))	상하한(Tight Bound)	상한=하한	정확한 성능 표현

수식 관계

f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) AND f(n) = Ω(g(n))
즉, 빅세타는 빅오와 빅오메가가 동시에 성립할 때 사용하며, 알고리즘의 정확한 점근적 복잡도를 나타낸다.

시험 포인트

기술사 시험에서는 빅오(O) 표기가 가장 빈출. "알고리즘 복잡도가 O(n²)이다"는 최악의 경우 n²에 비례한다는 의미. 빅세타는 상·하한이 일치하는 합병정렬(Θ(n log n)) 설명 시 활용한다.

Ⅳ.결론

Conclusion

알고리즘 복잡도 분석은 효율적인 알고리즘 설계와 선택의 핵심 기준이다. 빅오(O) 표기법은 최악의 성능 상한을 정의하고, 빅오메가(Ω)는 하한, 빅세타(Θ)는 정확한 점근적 복잡도를 나타낸다. 실무에서는 최악의 경우를 기준으로 O(n log n) 이하를 목표로 알고리즘을 설계하며, 시간복잡도와 공간복잡도 간의 트레이드오프를 고려해야 한다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록