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

어떤 알고리즘의 성능을 보기위해 복잡도를 분석하는데 무엇을 중점에 두어 분석하냐에 따라 크게 시간 복잡도와 공간 복잡도로 나뉜다.

이를 표기하는 방법에는 여러가지가 있는 데 대체로 빅오(O)와 세타( Θ)표기법이 쓰이며, 빅오가 가장 많이 쓰인다.

표기법에 대한 설명 보기

아래의 사진은 빅오의 복잡도 그래프 이며 O(1) 부터 ~ O(n!)순으로 복잡도가 증가하게 된다.

시간 복잡도라면 뒤로 갈수록 시간이 오래 걸리는 알고리즘.

공간 복잡도라면 뒤로 갈수록 공간(자원)을 많이 사용하는 알고리즘.

(사진 출처 : https://www.bigocheatsheet.com/ )

◼ 시간 복잡도

---

어떠한 알고리즘을 수행하는 데 몇번의 연산이 이루어지는 지를 표기한 것.

연산 => 산술, 대입, 비교, 이동

여기서 연산의 개수는 입력한 데이터가 n이고, 이 n에 따른 연산의 개수를 함수로 나타낸 것이 시간 복잡도 함수이다.

◼ 공간 복잡도

---

어떠한 알고리즘을 완료하는데 필요로 하는 공간(자원)의 양.

총 요구하는 공간 = 고정 공간 + 가변 공간

- 고정 공간 : 입출력에 관계없는 공간 (코드 저장 공간, 상수, 고정 크기의 변수 )

- 가변 공간 : 알고리즘에 따라 변하는 크기를 가진 구조의 변수들을 위한 공간 ( 함수가 순환 호출 하거나 추가 배열을 생성하는 것과 같은 동적인 공간 )

좋은 알고리즘이란 시간 복잡도와 공간 복잡도가 좋은 알고리즘 ( 빠르고 자원의 사용도 적은 알고리즘 )

시간 복잡도와 공간 복잡도가 대체로 반비례 관계를 갖는다.

그 중간점을 잘 타협 하는 것이 중요하다.

또한, 최근에는 메모리(자원)이 많이 싸지게 되면서 공간을 어느정도 차지해도 시간이 빠른 알고리즘이 더 좋다.