배열의 메모리 구조 — 연속 메모리와 O(1) 접근

사물함 100개가 일렬로 나란히 있다고 상상해보세요. 37번 사물함을 찾으러 갈 때 1번부터 셀 필요가 있나요?

배열도 마찬가지입니다. 연속된 메모리 공간에 데이터가 나란히 저장되기 때문에 위치를 계산 한 번으로 바로 접근합니다

배열의 i번째 요소 주소는 한 줄 공식으로 구할 수 있습니다

덧셈과 곱셈 한 번씩이면 끝! 데이터가 1억 개여도 접근 시간은 동일합니다. 이것이 O(1) 시간복잡도입니다

배열과 연결 리스트를 시간복잡도로 비교해봅시다

Python의 list는 내부적으로 동적 배열(Dynamic Array)입니다

# 배열 기본 연산과 시간복잡도
arr = [10, 20, 30, 40, 50]

# O(1) — 인덱스 접근
print(arr[2])          # 30

# O(1) — 맨 뒤 추가
arr.append(60)         # [10, 20, 30, 40, 50, 60]

# O(n) — 맨 앞 삽입 (전체 시프트)
arr.insert(0, 5)       # [5, 10, 20, 30, 40, 50, 60]

# O(n) — 중간 삭제
arr.pop(3)             # [5, 10, 20, 40, 50, 60]

# O(1) — 길이 확인
print(len(arr))        # 6

배열에서 인덱스를 이용한 접근의 시간복잡도는?

Python list에서 맨 앞에 원소를 삽입하면 시간복잡도는?

배열의 크기가 클수록 인덱스 접근 시간도 오래 걸린다

Python의 list.append()는 평균적으로 O(1)이다

배열의 i번째 요소 주소 공식: address(i) = base_address + i × ____

배열의 i번째 요소 주소 공식: address(i) = base_address + i × ____

배열의 메모리 구조