복잡도란 ?
쉽게 말해서, 코드가 얼마나 빠르고 얼마나 많은 자원을 쓰는지 측정하는 척도이다.
자원 = 컴퓨터가 사용하는 “리소스”
주로 시간과 메모리 두가지를 의미한다.
실행 시간이 얼마나 오래 걸리는지, 메모리를 얼마나 차지하는지에 대한 것 !
복잡도가 왜 중요한가?
컴퓨터는 연산속도와 메모리 용량이 한정된다.
프로그램의 규모가 방대해질수록 처리해야하는 데이터 양이 많아지므로,
양이 많아질수록 알고리즘의 수행능력이 중요하게 작용한다.
→ 입력(N)이 커질수록 알고리즘이 느려지는지 판단해야 하기 때문이다.
→ 얼마나 효율적인 = 좋은 알고리즘인지를 판단하고 비교하기 위해 중요하게 사용된다.
- 코드가 얼마나 빠른지? : 시간복잡도
- 메모리를 얼마나 많이 차지 하는지? : 공간복잡도
시간복잡도
- 코드가 실행되는 데 걸리는 시간
- 시간 복잡도가 낮을수록 알고리즘이 빠르고 효율적으로 실행됨을 의미한다.
- 이를 측정하는 방법으로 가장 일반적으로 “big O” 표기법을 사용한다.
big-O 표기법
- 알고리즘의 시간 복잡도와 공간 복잡도를 수학적으로 표현하는 방식이다.
- 입력크기 N을 변수로, N이 커질수록 대략적으로 얼마나 커지는지를 표현하기 위해 사용한다.
- 최악의 경우 수행시간을 기준으로 표시한다.
이미 정렬된 카드 5장보다 흐트러진 카드 5장이 정렬하는 데 시간이 오래 걸린다. 이처럼 같은 입력 값 N이 들어왔을 때 시간복잡도는 모두 다르지만, 그중 최악의 경우 수행시간을 기준으로 한다. 최소한의 기준점이 되기 때문이다.
bigO 표기법이 무엇인가
- 알고리즘의 시간 복잡도와 공간 복잡도를 수학적으로 표현하는 방식이다.
- 입력크기 N을 변수로, N이 커질수록 대략적으로 얼마나 커지는지를 표현하기 위해 사용한다.
- 최악의 경우 수행시간을 기준으로 표시한다.
이미 정렬된 카드 5장보다 흐트러진 카드 5장이 정렬하는 데 시간이 오래 걸린다. 이처럼 같은 입력 값 N이 들어왔을 때 시간복잡도는 모두 다르지만, 그중 최악의 경우 수행시간을 기준으로 한다. 최소한의 기준점이 되기 때문이다.
어떻게 표기하는가?
- 입력 N이 무한히 커질 때를 가정하여 최고차항만을 남기고 그외 항 및 계수는 무시한다.
- f(n) = 5x^2 +3x-2 g(n) = 4x^3 - 6x 이 두 함수에서 n이 무한히 커졌을 때 f(n)의 값이 훨씬 커질 것이다. 이는 최고차항의 계수만을 보고 알 수 있다.
- 이처럼 Big-O는 알고리즘의 성능이 최악인 경우, 수행 시간의 상한을 나타낸다.
bigO의 종류
실행 속도 O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)
공간복잡도
- 코드가 사용하는 메모리 크기
- ram이 한정되어 있기 때문에, 대규모 데이터를 다룰 때 중요하다.
- 시간복잡도와 마찬가지로 빅오 표기법 사용
구성요소
- 입력
- 사용자가 넘겨주는 데이터
- 추가 사용 변수
- 호출 스택
arr = [5, 3, 8, 1] # 입력 배열 O(N)
temp = [0] * len(arr) # 임시로 만든 배열 O(N)시간복잡도 vs 공간복잡도
실제로는 시간과 공간을 모두 고려해야 하지만,
대부분의 경우 "시간 복잡도"를 더 중요하게 본다.
그 이유는 사용자의 체감 속도, 시간 제한 문제,
그리고 최근 하드웨어 환경에서 메모리 여유가 있기 때문이다.
- 현업에서는 상황에 맞게 시간/공간을 모두 최적화하는 능력이 중요!
시간 복잡도 vs 공간 복잡도 한눈에 비교
| 항목 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 의미 | 코드가 얼마나 빠르게 실행되는지 | 코드가 얼마나 많은 메모리를 사용하는지 |
| 중요성 | 사용자 체감 속도와 직결 | 제한된 환경(임베디드, 빅데이터)에서 중요 |
| 주요 지표 | 연산 횟수 / 반복문 / 재귀 깊이 | 배열, 딕셔너리, 큐 등 자료구조 사용량 |
| 표현 방식 | O(1), O(N), O(N log N) 등 | O(1), O(N), O(N²) 등 |
| 주로 신경 쓰는 경우 | 코딩테스트, API 응답속도, 서비스 UX | 메모리 제한이 빡빡한 경우 |
| 트레이드오프 | 공간을 더 써서 시간을 줄이기도 함 (ex: DP 메모이제이션) | 시간보다 공간을 아끼기 위해 느려지는 경우도 있음 (ex: 비트마스크) |
트레이드 오프
1. 시간 복잡도와 공간 복잡도 관계
Q. 둘이 항상 반비례일까?
- 꼭 그렇진 않다.
하지만 많은 경우에서는,
시간을 아끼기 위해 공간을 더 쓰거나
공간을 아끼려다 시간이 더 드는 경우가 많다.
➡ 그래서 일반적으로 "상대적으로 반비례하는 경향"이 있다.
2. 그래서 왜 트레이드오프를 하는가?
이유는 자원이 한정적이기 때문!
- 컴퓨터에는 시간 제한도 있고 메모리 제한도 있다.
- 둘 다 무제한으로 쓸 수 없으니까
➡ 상황에 맞게 “ 하나를 얻고, 다른 걸 포기 “
3. 트레이드 오프란?
- "시간을 줄이려면 공간을 쓰고"
- "공간을 아끼려면 시간이 더 걸리는"
이런 딜레마 상황을 트레이드오프라고 한다.
4. 대표적인 트레이드오프 사례
1) 다이나믹 프로그래밍 (DP) - 시간최적화
- O(N) 메모리 사용해서 → 시간 복잡도 O(N)으로 줄임
- 메모리를 덜 쓰려면 → O(2^N)처럼 중복 호출 발생
2) 캐싱 (메모이제이션) - 시간최적화
- 메모리를 더 사용해서 이전 결과를 저장
- 대신 속도가 O(1)에 가까움
3) in-place 정렬 - 공간최적화
- O(1) 공간으로 배열 안에서 직접 swap
- 대신 병합정렬처럼 빠르고 안정적인 속도는 보장하지 않을 수도 있음
이유민