array cost 배열 메모리 비용 모델 빠른 인덱스 조회는 연속 메모리 주소 계산에서 나오고, 느린 중간 변경은 원소 이동 비용에서 나온다.
빠른 확인 인덱스 조회, 중간 변경, 반복 구간 질의 중 무엇이 많은지 먼저 표시한다.
연산별 비용 원인
Base 연속 공간시작 주소와 원소 크기를 기준으로 같은 폭의 칸이 이어진다.
Index 주소 즉시 계산i번째 원소 주소는 base + i * size 형태로 바로 접근한다.
Cache 순차 접근 강점가까운 원소를 이어 읽으면 CPU 캐시 지역성을 활용하기 쉽다.
Shift 중간 변경 비용삽입과 삭제는 뒤 원소를 밀거나 당기는 이동량이 병목이 된다.
Prefix 반복 질의 보정구간 합처럼 반복 조회가 많으면 추가 배열로 조회 시간을 줄인다.
선택 단서 배열 문제는 이름보다 실제 연산 분포가 중요하다. 조회가 많으면 배열의 장점이 크고, 앞·중간 변경이 많으면 이동 비용을 먼저 계산한다.