시간복잡도 & 공간복잡도

알고리즘의 효율성을 평가하는 핵심 개념 → "시간"과 "메모리(공간)"

 

• 시간복잡도(Time Complexity) → 알고리즘이 실행되는 데 걸리는 시간
• 공간복잡도(Space Complexity) → 알고리즘이 사용하는 메모리 공간 크기

즉, 빠르고 효율적인 알고리즘을 찾으려면 "시간"과 "공간"을 모두 고려해야 한다.

---

1. 시간복잡도(Time Complexity)

입력 크기(n)에 따라 실행 시간이 어떻게 변하는지 나타내는 함수

• Big-O 표기법(O(n)) 을 사용하여 최악의 경우(Worst Case)를 표현

시간복잡도 종류

표기법	의미	예제
O(1)	상수 시간	리스트 첫 번째 요소 접근 (arr[0])
O(log n)	로그 시간	이진 탐색 (Binary Search)
O(n)	선형 시간	리스트 전체 탐색 (for 반복문)
O(n log n)	선형 로그 시간	퀵 정렬, 병합 정렬
O(n²)	제곱 시간	중첩 for 반복문 (버블 정렬)
O(2ⁿ)	지수 시간	피보나치 재귀 (비효율적)
O(n!)	팩토리얼 시간	외판원 문제 (TSP, 완전탐색)

 

입력 크기가 커질수록 O(n²) > O(n) > O(1) 순서로 실행 시간이 급격히 증가한다.

---

2. 공간복잡도(Space Complexity)

알고리즘이 실행되는 동안 사용하는 메모리의 크기

• 시간복잡도처럼 Big-O 표기법(O(n)) 을 사용
• 변수, 배열, 재귀 호출 등으로 인해 메모리가 사용됨

표기법	의미	예제
O(1)	상수 공간	변수 1~2개만 사용
O(n)	선형 공간	크기 n인 배열 사용
O(n²)	제곱 공간	n x n 크기의 2D 배열 사용
O(n!)	팩토리얼 공간	백트래킹 알고리즘

 

 

공간복잡도가 낮을수록 메모리를 절약할 수 있습니다.

---

시간복잡도와 공간복잡도는 트레이드오프 관계

• 빠르게 실행하려면 (O(1)) → 메모리를 더 사용해야 할 수도 있음 (O(n))
• 메모리를 절약하려면 (O(1)) → 실행 시간이 오래 걸릴 수도 있음 (O(n²))

---

최적의 방법 찾는 법

1. 입력 크기(n)가 크다면 O(n log n) 이하의 알고리즘을 고려하라
2. 캐싱(Hash Table, DP)을 사용할지 판단하라 (속도 vs 메모리 트레이드오프)
3. 탐색이 필요하면 이진 탐색을 고려하고, 정렬된 데이터를 활용하라
4. 정렬이 필요하면 O(n log n) 정렬을 사용하라
5. 재귀를 사용할 경우 메모리(stack)를 고려하고, 반복문으로 최적화할 수 있는지 확인하라

즉, 문제마다 "입력 크기", "시간 vs 공간", "반복 vs 재귀" 등을 고려해서 최적의 알고리즘을 선택해야 합니다.