array란 무엇이며, 그 연산들의 복잡도는 어떻게 되나요?

Question

Accepted Answer

**array(배열)**는 같은 타입의 원소들을 담고 있는 연속된 메모리 블록으로, `0`부터 인덱싱됩니다. 원소들이 서로 인접해 있기 때문에 원소 `i`의 주소는 `base + i * elementSize`로 직접 계산되며, 이로써 **O(1) 임의 접근**이 가능합니다.

## 메모리 레이아웃

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (4바이트 정수)
```

## 예시

```python
arr = [10, 20, 30, 40, 50]
x = arr[3]            # O(1) — 직접 인덱스 연산
arr.append(60)        # amortized O(1) (dynamic array)
arr.insert(0, 5)      # O(n) — 모든 원소를 오른쪽으로 이동
arr.pop(0)            # O(n) — 모든 원소를 왼쪽으로 이동
```

## 복잡도

| 연산 | 시간 |
|---|---|
| index로 접근 | O(1) |
| 검색(정렬 안 됨) | O(n) |
| Append(dynamic) | O(1) amortized |
| 앞/중간에서 insert/delete | O(n) |

## 트레이드오프

- **강점:** 빠른 인덱싱, 캐시 친화적(데이터가 연속됨), 낮은 메모리 오버헤드.
- **약점:** 중간에서의 삽입/삭제는 O(n); 고정 크기 array는 늘리려면 복사가 필요함.

## 왜 중요한가

array는 대부분의 다른 구조의 기반입니다. 문자열, hash table, heap, dynamic list 모두 array 위에 만들어집니다.

array의 캐시 지역성 덕분에 실제 벤치마크에서는 "더 느린" Big-O를 가진 array가 "더 빠른" 포인터 기반 구조를 이기는 경우가 많습니다.

연산	시간
index로 접근	O(1)
검색(정렬 안 됨)	O(n)
Append(dynamic)	O(1) amortized
앞/중간에서 insert/delete	O(n)