[자료구조] 복잡도

자료구조(Data Structure)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다.

이러한 자료구조를 사용할 때 크게 두가지의 복잡도를 고려하며 사용하게 되는데, 바로 시간 복잡도와 공간 복잡도이다.

 

앞서 복잡도를 나타낼 때 사용하는 표기법인 빅오 표기법(O(n))이 있다. 빅오 표기법은 입력 범위 n이라는 것이 주어졌을 때 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것을 의미한다. 표기하는 방법은 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 계산한다. 왜냐하면 증가 속도를 고려할 때 가장 영향을 많이 끼치는 항의 상수 인자를 제외하고 미미하기 때문이다.

 

 

시간복잡도(Time Complexity)

• 알고리즘이 실행되는 데 걸리는 시간을 측정한 것이다. 입력 크기(n)에 따라 알고리즘이 수행해야 할 기본 연산의 횟수를 나타낸다.
• 예를 들어, O(1), O(n), O(n^2)와 같은 표기법을 사용한다. 여기서 O(1)은 입력 크기에 상관없이 일정한 시간이 걸리는 경우를, O(n)은 입력 크기에 비례해 시간이 증가하는 경우를 의미한다.

공간복잡도(Space Complexity)

• 알고리즘이 실행되는 동안 필요한 메모리 양을 측정한 것이다. 마찬가지로 입력 크기(n)에 따라 필요한 메모리 양이 어떻게 변하는지를 나타낸다.
• 예를 들어, O(1)은 일정한 메모리를 사용하고, O(n)은 입력 크기에 비례해 메모리 사용량이 증가하는 경우를 의미한다.

다음은 자료구조에서의 시간 복잡도를 나타낸 테이블이다.

 

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

자료구조	접근 (Access)	탐색 (Search)	삽입 (Insertion)	삭제 (Deletion)
배열 (Array)	O(1)	O(n)	O(n)	O(n)
연결 리스트 (Linked List)	O(n)	O(n)	O(1)	O(1)
스택 (Stack)	O(1)	O(n)	O(1)	O(1)
큐 (Queue)	O(1)	O(n)	O(1)	O(1)
해시 테이블 (Hash Table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리 (Binary Search Tree)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리 / 레드-블랙 트리 (AVL Tree / Red-Black Tree)	O(log n)	O(log n)	O(log n)	O(log n)
힙 (Heap)	O(n)	O(n)	O(log n)	O(log n)
트라이 (Trie)	O(m)	O(m)	O(m)	O(m)

 

자료구조의 최악의 시간 복잡도

자료구조	접근 (Access)	탐색 (Search)	삽입 (Insertion)	삭제 (Deletion)
배열 (Array)	O(1)	O(n)	O(n)	O(n)
연결 리스트 (Linked List)	O(n)	O(n)	O(1)	O(1)
스택 (Stack)	O(n)	O(n)	O(1)	O(1)
큐 (Queue)	O(n)	O(n)	O(1)	O(1)
해시 테이블 (Hash Table)	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리 (Binary Search Tree)	O(n)	O(n)	O(n)	O(n)
AVL 트리 / 레드-블랙 트리 (AVL Tree / Red-Black Tree)	O(log n)	O(log n)	O(log n)	O(log n)
힙 (Heap)	O(n)	O(n)	O(log n)	O(log n)
트라이 (Trie)	O(m)	O(m)	O(m)	O(m)

 

자주 쓰는 자료구조의 시간 복잡도를 생각할 때 평균, 최악의 시간 복잡도를 고려하면서 사용한다.