23.09.13 시간 복잡도와 공간 복잡도

시간 복잡도 (Time Complexity)

 알고리즘이 실행되는 데 얼마나 시간이 걸리는지를 나타내는 지표이다. 이는 일반적으로 입력 크기에 대한 함수로 표현되는데, Big-O 표기법이 자주 사용된다.

 

예시

• O(1): 상수 시간 (Constant time)
• O(log n): 로그 시간 (Logarithmic time)
• O(n): 선형 시간 (Linear time)
• O(n^2): 제곱 시간 (Quadratic time)
• O(2^n): 지수 시간 (Exponential time)

 

참고

• Big-O (O): 알고리즘의 최악의 경우를 평가 ("빅 오")
• Big-Θ (Θ): 알고리즘의 평균적인 경우를 평가 ("빅 세타")
• Big-Ω (Ω): 알고리즘의 최선의 경우를 평가 ("빅 옴")

 

공간 복잡도 (Space Complexity)

알고리즘의 실행에 필요한 메모리 양을 나타낸다. 시간 복잡도와 유사하게, 공간 복잡도도 Big-O 표기법으로 표현될 수 있다.

예시:

• O(1): 알고리즘 실행에 추가 공간이 상수로 필요한 경우
• O(n): 알고리즘 실행에 입력 크기와 비례하는 추가 공간이 필요한 경우

예시

1. 선형 검색 (Linear Search)
   • 시간 복잡도: O(n)
   • 공간 복잡도: O(1)
2. 이진 검색 (Binary Search)
   • 시간 복잡도: O(log n)
   • 공간 복잡도: O(1) (반복 구현의 경우), O(log n) (재귀 구현의 경우)
3. 버블 정렬 (Bubble Sort)
   • 시간 복잡도: O(n^2)
   • 공간 복잡도: O(1)
4. 퀵 정렬 (Quick Sort)
   • 시간 복잡도: 평균 O(n log n), 최악의 경우 O(n^2)
   • 공간 복잡도: O(log n) (반복 구현의 경우), O(n) (재귀 구현의 경우)

요약

• 시간 복잡도: 알고리즘이 얼마나 빠르게 동작하는지를 측정
• 공간 복잡도: 알고리즘이 얼마나 많은 메모리를 사용하는지를 측정

 

트레이드오프 (Trade-Off)

시간 복잡도와 공간 복잡도는 종종 트레이드오프 관계에 있다. 예를 들어, 캐싱을 통해 시간 복잡도를 줄일 수 있지만, 이는 추가적인 메모리 공간이 필요하기 때문에 공간 복잡도가 증가할 가능성이 높다.

 

여기서 나는 의문이 들었다. 위에서 Big-Θ (Θ)와 시간 복잡도: 평균 O(n log n), 최악의 경우 O(n^2) 같은 평균이라는 말을 쓰는데 뭐가 다를까 하는 부분이다.

 

 평균 시간 복잡도는 알고리즘이 다양한 입력에 대해 얼마나 일반적으로 성능을 나타내는지에 대한 추정치이다. 따라서 주어진 입력 분포에 따라 다를 수 있으며, 수학적인 평균과 다르다.

 

 Big-Θ (Θ) 표기법은 알고리즘의 "평균적인 경우"를 나타내는 것이 아니라, 알고리즘의 시간 복잡도가 어느 정도 "정확히" 어떤 함수와 일치하는지를 나타낸다. 즉, Big-Θ는 알고리즘의 상한과 하한이 동일할 때 사용하는 표기법이다. Big-O는 상한을, Big-Ω는 하한을 나타내며, Big-Θ는 두 개가 일치할 때 사용한다. 예를 들어, 알고리즘 A의 시간 복잡도가 최악의 경우 O(n^2), 최선의 경우 Ω(n)일 때, 평균적으로 n log n이라고 해도 이를 Θ(n log n)이라고 표현하지는 않는다.

 

둘 다 중요하고, 상황에 따라 다르겠지만 일반적으로 우선 순위를 정하자면 시간 복잡도를 더 중요하게 생각한다.