[알고리즘, 자료구조] 시간복잡도

시간 복잡도 (Time complexity)

시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수관계를 가르킨다. 어떠한 알고리즘의 로직이 얼마나 오랜시간이 걸리는지를 나타내는데 쓰이며 보통 빅오표기법으로 나타낸다.

 

시간복잡도의 존재이유

시간복잡도는 효율적인 코드로 개선하는데 쓰이는 척도가 된다.

https://velog.io/@shitaikoto/Algorithm-Time-complexity

그림과 같이 O(1)과 O(n)은 입력크기가 커짐에 따라 차이가 발생하고, O(nlogn)의 경우 더 많은 차이를 볼 수 있다. 이처럼 입력의 크기가 커짐에 따라 너무 많은 시간이 들어가는 시간복잡도를 가진 알고리즘은 피해야 한다.

 

자료구조의 평균 시간복잡도

자료구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(n)	O(n)	O(n)
스택(Skack)	O(n)	O(n)	O(1)	O(1)
큐(Queue)	O(n)	O(n)	O(1)	O(1)
이중연결리스트(Doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시테이블(Hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(nlogn)	O(nlogn)	O(nlogn)	O(nlogn)
AVL트리	O(nlogn)	O(nlogn)	O(nlogn)	O(nlogn)
레드블랙트리	O(nlogn)	O(nlogn)	O(nlogn)	O(nlogn)

---

공간복잡도 (Space complexity)

공간복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다. 정적 변수로 선언된 것 말 고 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함된다.

---

시간 복잡도가 낮지만 공간 복잡도가 높은 경우 대처법

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

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

빅데이터를 처리하는 경우 공간복잡도가 커지게 된다면 메모리에 한번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이 경우 데이터를 나눠서 처리하고 다시 합치는 방법을 사용한다.