array memory
배열은 연속 슬롯이라 위치 접근은 빠르고 중간 삽입은 비싸다
인덱스는 주소 계산으로 바로 닿지만, 중간에 값을 넣으면 뒤 원소들이 한 칸씩 이동한다.
base + i
shift
연속 메모리 슬롯
base+0A[0]
base+1A[1]
base+2A[2]
base+3A[3]
base+4A[4]
base+5A[5]
중간 삽입이 비싼 이유
100
201
Xinsert
30 →shift
40 →shift
50 →shift
| 연산 | 비용 | 이유 |
|---|---|---|
| 인덱스 접근 | O(1) | base + i * sizeof(T)로 위치를 바로 계산한다. |
| 순차 순회 | O(N) | 연속 슬롯을 앞에서 뒤로 한 번 훑는다. |
| 중간 삽입/삭제 | O(N) | 뒤 원소들을 밀거나 당겨야 한다. |
| prefix sum | 전처리 O(N), 구간합 O(1) | 원본 배열 위에 누적 배열을 하나 더 둔다. |
점검: 끝 삽입은 빠를 수 있지만, 중간 삽입이 많으면 연결 리스트나 다른 구조를 비교한다.