1. 배열 (Array)

✅ 검색: O(1)

• 원리: 배열은 연속된 메모리 공간을 사용하여, 인덱스를 기반으로 즉시 접근할 수 있음.

• 동작 방식: 배열의 시작 주소(base_address)에 인덱스 크기만큼 오프셋을 추가하여 직접 접근.

  • 예를 들어, 배열 arr[5]의 주소 계산: 주소=base_address+(index×size_of_each_element)

    주소=base_address+(index×size_of_each_element)\text{주소} = \text{base\_address} + (\text{index} \times \text{size\_of\_each\_element})

• 결과: 검색이 항상 O(1).

✅ 삽입/삭제: O(N)

• 원리: 중간에 요소를 삽입하거나 삭제할 경우, 연속된 메모리 구조를 유지하기 위해 요소들을 이동해야 함.
• 삽입 예시 (arr.insert(index, value))
  • 중간(예: 3번째 위치)에 요소를 추가하면, 기존 요소들을 뒤로 이동(O(N)) 후 새로운 값 추가.
• 삭제 예시 (arr.erase(index))
  • 중간(예: 3번째 위치) 요소 삭제 시, 나머지 요소를 앞으로 이동(O(N)).

2. 배열 리스트 (Array List, std::vector)

배열 기반 리스트는 배열과 동일한 검색(O(1)) 속도를 가지지만, 크기 조정 시 동적 할당과 복사가 발생할 수 있음.

✅ 검색: O(1)

• 원리: 배열처럼 인덱스를 통해 즉시 접근 가능.

✅ 삽입/삭제: O(N) (평균적으로 O(1) 가능)

• 삽입:
  • 맨 끝(push_back): O(1) (단, 배열 크기를 초과하면 O(N) 재할당)
  • 중간 삽입: 기존 요소들을 뒤로 이동해야 하므로 O(N)
• 삭제:
  • 맨 끝 삭제(pop_back): O(1)
  • 중간 삭제: O(N) (앞 요소를 한 칸씩 당겨야 함)