시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

| 시간복잡도(Time Complexity)란?

• 시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는 척도이다.
• 알고리즘의 실행 시간은 입력 데이터의 크기나 특성에 따라 다를 수 있기 때문에, 시간 복잡도는 일반적으로 최악의 경우, 평균 경우, 최선의 경우로 나누어 평가된다.

 

빅-오 표기법(Big O Notation)

: 시간 복잡도를 표현하는데 가장 일반적으로 사용되는 표기법이다. 빅 오 표기법은 알고리즘 성능에 가장 큰 영향을 미치는 부문만을 고려하여 나타낸다. 예를 들어, 동전을 던져 뒷면이 나올 확률을 이야기할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안좋을 경우 n번 만큼 동전을 던저야 한다. 이런 확률에서 최악의 경우를 계산하는 방식을 빅오 표기법이라 한다.

 

 

자주 사용되는 시간 복잡도의 예

• O(1): 상수 시간. 입력 데이터의 크기와 상관없이 일정한 시간이 소요된다.
• O(log n) : 로그 시간. 이진 검색과 같은 알고리즘에서 나타난다.
• O(n) : 선형 시간. 단순 검색과 같은 알고리즘에서 나온다.
• O(n log n): 병합 정렬 또는 퀵 정렬과 같은 알고리즘에서 나온다.
• O(n²) : 다항 시간. 버블 정렬, 삽입 정렬, 선택 정렬 등에서 나타난다.
• O(2ⁿ) : 알고리즘의 시간 복잡도나 공간 복잡도가 입력 크기에 지수적으로 증가한다. 매우 비효율적이며 입력 크기가 작은 경우에만 실제로 실행이 가능하다. ex)피보나치 수열의 재귀적 구현, 이중 for문

[faster]    O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ)    [slower]

 

---

| 공간복잡도(Space Complexity)란?

• 공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 양을 나타내는 척도이다.
• 시간 복잡도와 마찬가지로 공간 복잡도도 빅 오 표기법을 사용해 표현한다.

 

공간 복잡도의 구성

• 고정 공간(Fixed Space): 알고리즘의 실행에 필요한 고정된 크기의 메모리이다. 예를 들면 변수, 상수, 간단한 데이터 구조 등이다.
• 가변 공간(Variable Space) : 알고리즘 실행에 따라 크기가 변하는 메모리이다. 예를 들면 재귀 스택, 동적 할당된 메모리 등이다.

 

---

| 정리

• 시간 복잡도와 공간 복잡도는 종종 trade-off 관계에 있다. 즉, 시간을 절약하기 이해 더 많은 메모리를 사용하거나, 메모리를 절약하기위해 더 많은 시간을 소비하는 것이다. 이러한 trade-off를 특정 문제나 상황에 따라 다르게 선택해야한다.