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

[ 참고용: 시간복잡도 ]

출처: https://erinh.tistory.com/entry/자료구조-Java-시간복잡도-점근표기법-빅오표기법?category=1046468 

공간복잡도란?

: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양

- 정적 변수로 선언된 것 외에, 동적인 재귀적 함수로 인해 공간을 계속해서 필요로 할 경우도 포함

- 시간복잡도와 마찬가지로 빅오표기법을 사용

- int 자료형 기준으로 배열 크기에 따른 메모리 사용량을 일반적으로 아래와 같음

int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB

자료구조에서의 시간 복잡도

1. 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
이진 탐색 트리	O(n)	O(n)	O(n)	O(n)

2. 평균 시간 복잡도

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(log n)