배열 (Array)

값이 연속된 메모리에 같은 크기로 놓여 있어서 주소를 계산으로 구할 수 있습니다.

주소 = 시작 주소 + (인덱스 x 원소 크기)

int 배열이 100번지에서 시작하면
  arr[0] -> 100,  arr[3] -> 112,  arr[999] -> 4096

몇 번째든 곱셈 한 번과 덧셈 한 번이라 인덱스 크기와 무관합니다. 이것이 O(1)의 근거입니다.

이 성질은 두 조건에 의존합니다. 원소 크기가 모두 같아야 하고 연속 배치여야 합니다. 그래서 배열은 만들 때 크기를 정해 한 덩어리로 잡습니다.

흔한 실수: "배열은 빠르니까 O(1)"처럼 결론만 말하는 것. 면접에서는 주소 계산식을 대는 것이 답입니다. 참조 배열(객체 배열)이라도 저장하는 것은 같은 크기의 참조값이므로 계산은 동일합니다.

용량이 차면 더 큰 배열을 새로 만들어 옮깁니다. 보통 1.5배나 2배로 늘립니다.

용량 4, 크기 4에서 하나 더 추가
  1. 용량 8인 배열을 새로 만든다
  2. 기존 4개를 복사한다
  3. 새 값을 넣는다

복사가 O(n)인데도 추가 연산을 분할상환 O(1)이라 부르는 이유는, 확장이 드물게 일어나고 그 비용을 그 사이의 값싼 추가들에 나눠 담을 수 있기 때문입니다. 용량이 배수로 늘어나므로 n개를 넣는 동안 총 복사량은 2n 안쪽입니다.

흔한 실수: 배수 대신 고정값(예: 매번 +10)으로 늘려도 된다고 답하는 것. 그러면 확장 횟수가 n에 비례해 총 복사량이 n의 제곱이 되고 분할상환 O(1)이 깨집니다. 크기를 미리 알면 처음부터 지정해 확장을 없애는 것이 가장 좋습니다.

같은 O(n) 순회라도 실제 시간이 크게 다릅니다. 원인은 캐시 라인입니다.

마지막 줄이 특히 큽니다. CPU는 다음에 읽을 주소를 예측해 미리 가져오는데, 연결 리스트는 주소를 알기 위해 현재 노드를 먼저 읽어야 해서 이 예측이 통하지 않습니다.

흔한 실수: 복잡도 표만 보고 "삽입이 많으면 무조건 연결 리스트"라고 답하는 것. 원소 수가 수천 이하면 배열의 복사가 캐시 미스보다 싸서 배열이 이기는 경우가 많습니다.

연속 배치를 유지해야 하므로 빈 자리를 만들려면 뒤쪽 원소를 모두 한 칸씩 밀어야 합니다.

[10, 20, 30, 40, 50] 의 인덱스 1에 15를 넣는다
  50, 40, 30, 20 을 차례로 한 칸 뒤로 옮긴다   <- 옮기는 개수가 n에 비례
  빈 1번 자리에 15를 넣는다

맨 앞에 넣으면 전부 밀어야 하고, 맨 뒤에 넣으면 밀 것이 없어 O(1)입니다. 그래서 평균은 n의 절반이고 복잡도로는 O(n)입니다.

이 성질이 배열의 O(1) 접근과 맞바꾼 대가입니다. 주소를 계산으로 구하려면 연속이어야 하고, 연속을 유지하려면 옮겨야 합니다.

흔한 실수: 삭제는 값을 지우면 끝이라 O(1)이라고 답하는 것. 삭제도 빈 구멍을 메우려면 뒤를 앞으로 당겨야 해서 O(n)입니다. 순서가 중요하지 않다면 마지막 원소를 그 자리로 옮기고 크기를 줄여 O(1)로 만들 수 있습니다.