정적 배열
크기가 고정되어 있고 배열에 들어갈 수 있는 요소의 갯수에 제한이 있는 자료 구조이다.
동적 배열
크기가 변하고 배열에 요소를 계속 추가할 수 있는 자료 구조이다.
정적 배열과 동적 배열의 비교
연산에 따른 시간 복잡도
| 정적 배열 | 동적 배열 | |
|---|---|---|
| 접근 | O(1) | O(1) |
| 탐색 | O(n) | O(n) |
| 삽입 | 불가 | O(n), 맨 뒤에 삽입할 경우 O(1) |
| 삭제 | 불가 | O(n), 맨 뒤에 삭제할 경우 O(1) |
낭비하는 공간
- 정적 배열은 크기가 고정되어 있기 때문에 낭비하는 공간이 없다.
- 동적 배열은 공간을 낭비할 수도 있고 낭비하지 않을 수도 있다.
- 낭비하는 공간이 0일 수도 있고, 새로운 배열을 만들 때와 같은 최악의 경우에 낭비되는 공간은 n-2개가 될 수도 있다.
- 따라서 O(n)만큼의 공간이 낭비된다고 볼 수 있다.
