[CS/Computer Science][자료구조/Data Structure] 시간복잡도 / 공간복잡도

시간복잡도 및 공간복잡도는 자료구조 및 알고리즘을 판단하는 척도이다. 이 두 개념을 알아보기에 앞서, 자료구조와 알고리즘에 대해 먼저 개략적으로 짚고 넘어가 보자.

1. 자료구조 개요

자료구조는 컴퓨터 과학을 이해하는 데에 가장 중요한 개념 중 하나이다. 또한, 이와 함께 프로그래밍에서 목적을 이루기 위한 개념으로서 알고리즘이 있다.

개발자가 프로그래밍을 하는 데에 있어서, 자료구조와 알고리즘의 고려 여부에 따라 프로그램의 성능이 달라진다. → 이를 판단할 수 있는 척도가 시간복잡도 및 공간복잡도이다.

입력의 크기에 따른 프로그램 실행 시간의 관계

코드를 통한 이해

→ $n$번의 연산: $O(n)$

for _ in range(n):    # n번의 연산을 수행
	1 + 1             # '1+1'이라는 연산을

→ $2n$번의 연산: $O(2n) (= O(n))$

for _ in range(2*n):    # n번의 연산을 수행
	1 + 1             # '1+1'이라는 연산을

→ $n^2$번의 연산: $O(n^2)$ - 두 개의 반복문이 겹쳐져 “$n$번의 연산이 각 $n$번씩 발생”

for _ in range(n):        # n번의 연산을 수행
	for _ in range(n):    # n번의 연산에 대해, 각 n번의 연산을 수행
		1 + 1               # '1+1'이라는 연산을

⇒ 반복문이 시간 복잡도에 가장 큰 영향을 미친다.

시간복잡도가 $O(n)$인 임의의 연산에 대해, 입력의 크기(연산횟수) $n$은 매 연산 시도마다 달라질 수 있음

$O(n)$이라면, 그 알고리즘은 평균적으로 $n$번의 연산을 수행하는 것임
- $n$이 100이더라도, 100번 모두 수행해야 연산을 끝마치는 경우도 있을 것이고,
- $n$이 10000이더라도, 운이 좋게 1번만에 연산을 끝마칠 수도 있음
- But, 상황에 따라 판단이 들쭉 날쭉 해진다면 이는 제대로 된 성능 판단 척도로서 기능 불가 → 표기법의 기능

빅 오 표기법 (Big O notation)
- 가장 대중적인 표현
- 함수의 점근적 상한을 표기하는 방법
- 점근적 상한 - $n$이 무한대로 커진다고 할 경우, 증가하는 실행 시간의 한계
- 표기법:
  - $O(n)$ → “$n$이 아무리 증가해도, 실행시간의 증가율이 $n$보다는 작다.”
  - $O(n^2)$ → “$n$이 아무리 증가해도, 실행시간의 증가율이 $n^2$보다는 작다.”
- 유의사항
  - 점근적 상한 표기시, 최고차항의 차수만 고려함 (=n이 무한대로 커진다면, 최고차항 이외의 항들이 미치는 영향은 무시할 수 있음-극한)
빅 세타 표기법 (Big $\theta$ notation)
- 입력 $N$에 대한 평균적인 실행 시간을 표기하는 방법
- 표기법
  - $\theta(n)$ → “$n$이 증가해도, 실행시간의 증가율은 $n$과 같다.”
  - $\theta(n^2)$ → “$n$이 증가해도, 실행시간의 증가율은 $n^2$과 같다.”
빅 오메가 표기법 (Big $\Omega$ notation)
- 입력 $N$에 대한 점근적 하한을 표기하는 방법
- 표기법
  - $\Omega(n)$ → “$n$이 증가해도, 실행시간의 증가율은 $n$보다 크다.”
  - $\Omega(n^2)$ → “$n$이 증가해도, 실행시간의 증가율은 $n^2$보다 크다.”

연산의 횟수에 따른 점근적 상한 및 빅 오 표기법 정리

$O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)$

프로그램 실행 시, 필요한 메모리 자원의 양
모든 프로그램은 실행 시 메모리에 적재되어야 하므로, 실행 시 프로그램이 차지하는 용량에 따라 공간복잡도 표현됨
- 시간복잡도 - 입력에 따른 실행 시간의 척도
- 공간복잡도 - 입력에 따른 메모리 사용량의 척도
표기법 - 빅 오 표기법(시간복잡도와 동일)
오늘날 알고리즘 성능 판단의 척도는 공간 복잡도 보다는 시간복잡도

다음 글부터, 본격적으로 7가지 핵심적인 자료구조에 대해 하나씩 정리해 보겠습니다.