<aside> 💡 배열(array)은 번호(index)와 번호에 대응하는 데이터(value)로 이뤄진 자료구조를 나타낸다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호(index)가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

배열의 첫번째 요소의 메모리 주소를 첫번째 주소, 또는 기본 주소라고 한다.

</aside>

배열(array) 시간복잡도

• 접근: O(1)
  • 배열에서 접근: n번째 인덱스에 해당하는 값을 찾아내는 연산
  • 인덱스 기반으로 접근하기 때문에 특정 데이터의 인덱스를 알고 있다면 O(1)의 시간복잡도로 접근 가능
  • How? 배열의 첫번째 변수에는 시작 주소값이 들어있고 배열은 메모리에서 선형적으로 공간을 차지함. → (시작 주소값 + n) ⇒ 타겟 인덱스의 주소값이므로 사칙연산만으로 주소값에 접근 가능.
  • 연결리스트와 차이: random access가 가능하다는 점!
• 검색: O(n)
  • 타겟 데이터가 배열 안에 들어있는지 검색하는 연산.
  • 타겟 데이터가 배열 내에 있는지 모르기 때문에 인덱스를 알지 못함. 따라서 순차적으로 배열 내의 값과 타겟 데이터를 일일이 비교. 끝까지 다 비교할 경우 최대 n번의 비교가 필요하기 때문에 O(n)의 시간복잡도가 소요
• 삽입: O(1)(배열 내 빈 공간 존재하고 해당 인덱스를 명확하게 알 경우) / O(n) (배열 내 빈 공간이 존재하지 않을 때

  • 주의: 삽입/삭제는 배열 내에 빈 공간이 전제되어 있을 때를 기준. why? 배열은 고정 크기를 갖기 때문.

    • 해당 언어에서 어떤 형태의 배열(동적/정적)을 제공하냐에 따라 달라짐.
      • 파이썬: 동적 배열. 초기에는 크기를 작게 잡고 크기를 늘려야 할 필요가 있으면 더블링 방식으로 사이즈를 늘린다. 초반에는 2배로 늘리나 전체적으로는 약 1.12배의 비율로 늘림.
      • C: 정적 배열. 처음에 배열 선언 시 크기가 고정. 추가로 데이터가 필요하면 동적할당(malloc, realloc)을 통해 배열 크기를 늘린다.

  • 만약 빈 공간이 없다면? → 정적 배열이든 동적 배열이든 둘다 공간을 늘려줘야 함.

    • 여기서 주의: 동적 배열이라고 해서 기존 공간에 그대로 붙여서 늘리는 게 아니라 새 공간을 할당하고 거기에 데이터를 옮기는 식으로 진행.
• 삭제 시간복잡도: O(n)