시간 복잡도 & 공간 복잡도

동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 합니다.
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

---

시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다.

시간복잡도의 빅-오 표기법

시간 복잡도에는 빅-오 표기법이라는 개념이 나옵니다.

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.

이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.

---

시간 측정 방법

import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

위 코드로 측정 시간과 측정 종료 시간을 비교하여 확인할 수 있습니다.

---

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다.

시간과 공간은 반비례적 경향이 있음
최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
알고리즘은 시간 복잡도가 중심

공간 복잡도를 줄이는 방법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼칩니다.

프로그램에 필요한 공간은 크게

1. 고정 공간
2. 가변 공간

이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다.

---

💟참고자료
시간/공간복잡도