시간 복잡도, 공간 복잡도

복잡도: 알고리즘의 성능을 나타내는 척도

 

시간 복잡도

특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미한다.

 

---

Big-O 표기법 표

시간	복잡도명칭	예시	설명
O(1)	상수 시간 (Constant)	딕셔너리 조회, 리스트 인덱싱 등	입력 크기와 상관없이 항상 일정한 시간
O(log n)	로그 시간 (Logarithmic)	이진 탐색	입력이 커져도 느리게 증가
O(n)	선형 시간 (Linear)	배열 순회, 선형 탐색 등	입력 크기에 비례하여 시간 증가
O(n log n)	로그 선형 시간	퀵 정렬(평균), 병합 정렬 등	효율적인 정렬 알고리즘이 사용하는 복잡도
O(n²)	이차 시간 (Quadratic)	버블 정렬, 삽입 정렬, 이중 반복문	중첩 반복문에서 자주 발생
O(2ⁿ)	지수 시간 (Exponential)	재귀 피보나치, 부분 집합 생성	입력이 조금만 커져도 시간 급증
O(n!)	팩토리얼 시간 (Factorial)	순열, 조합, 외판원 문제(Brute-force)	가장 느린 복잡도, 가능한 모든 경우 탐색

---

 

 

• 입력 크기 n이 커질수록 차이가 극적으로 나타난다.
• 현실적인 알고리즘은 보통 O(n log n) 이내로 설계되어야 한다.
• 빅오 표기법은 최악의 경우 시간 복잡도를 의미하는 경우가 많다.