[Java] 자료구조의 시간복잡도와 공간복잡도

소개

자바에서 제공되는 주요 자료구조들의 일반적인 시간 복잡도를 살펴보겠습니다.

 

시간 복잡도란

알고리즘이 입력 크기에 따라 어떻게 성장하는지를 나타내는 개념입니다. 알고리즘의 성능을 분석하고 비교하기 위해 사용됩니다. 일반적으로, 알고리즘의 수행 시간이나 실행 단계 수를 입력 크기에 대한 함수로 표현합니다.

 

자료구조

Array

공간 복잡도: O(n)

• 배열은 각 원소를 연속된 메모리 위치에 저장하므로 모든 원소를 저장하기 위해서는 배열의 크기에 비례한 메모리가 필요합니다.

접근 (Access)	O(1)
검색 (Search)	O(n)
삽입 (Insertion)	O(n) - 평균적인 경우
삭제 (Deletion)	O(n) - 평균적인 경우

 

LinkedList

공간 복잡도: O(n)

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 노드의 개수에 비례한 메모리가 필요합니다.

접근 (Access)	O(n)
검색 (Search)	O(n)
삽입 (Insertion)	O(1) - 특정 위치에 노드를 삽입할 때
삭제 (Deletion)	O(1) - 특정 위치의 노드를 삭제할 때

 

HashSet:

접근 (Access)	O(1)
검색 (Search)	O(1) - 평균적인 경우
삽입 (Insertion)	O(1) - 평균적인 경우
삭제 (Deletion)	O(1) - 평균적인 경우

 

TreeSet:

접근 (Access)	O(log n)
검색 (Search)	O(log n)
삽입 (Insertion)	O(log n)
삭제 (Deletion)	O(log n)

 

HashMap:

공간 복잡도: O(n)

• 충돌을 해결하기 위해 각 버킷에는 여러 개의 원소가 저장될 수 있습니다. 이로 인해 해시 테이블의 크기에 비례한 메모리가 필요합니다.

접근 (Access)	O(1)
검색 (Search)	O(1)
삽입 (Insertion)	O(1)
삭제 (Deletion)	O(1)

 

TreeMap:

공간 복잡도: O(n)

• 각 노드는 자식 노드를 가리키는 포인터 등을 포함하므로 노드의 개수에 비례한 메모리가 필요합니다.

접근 (Access)	O(log n)
검색 (Search)	O(log n)
삽입 (Insertion)	O(log n)
삭제 (Deletion)	O(log n)

 

PriorityQueue:

공간 복잡도: O(n)

• PriorityQueue의 내부 구현은 힙으로서, 힙의 성질을 유지하기 위해 일정한 공간이 필요합니다. 원소를 삽입할 때마다 힙의 구조를 유지하기 위한 추가적인 배열 공간이 필요하게 됩니다.

접근 (Access)	O(n)
검색 (Search)	O(n)
삽입 (Insertion)	O(log n)
삭제 (Deletion)	O(log n)

 

Queue

공간 복잡도:

• O(n) - 큐에 저장된 원소의 개수에 비례

접근 (Access)	O(log 1)
검색 (Search)	O(log 1)
삽입 (Insertion)	O(log 1)
삭제 (Deletion)	O(log 1)

 

Stack

공간 복잡도:

• O(n) - 스택에 저장된 원소의 개수에 비례

접근 (Access)	O(log 1)
검색 (Search)	O(log 1)
삽입 (Insertion)	O(log 1)
삭제 (Deletion)	O(log 1)