배열이 조회 연산에 강점을 보이는 이유

by 지원
…
끄적임
|
이야기

조회 연산이 잦은 경우 배열(Array) 자료구조가 좋은 선택이 될 수 있다. 배열의 경우 데이터(원소) 접근의 시간복잡도가 O(1)으로 인덱스를 사용하여 빠르게 조회가 가능하다.

arr = [17, 34, 51]
puts arr[0] # => 첫 번째 원소 '17' 출력
puts arr[1] # => '34'
puts arr[2] # => '51'

빠른 조회가 가능한 이유는 배열은 메모리에 하나의 연속된 블럭으로 할당되기 때문이다. 예를들어 크기 3인 배열의 경우, 메모리를 뜯어 보면 3개의 데이터를 저장할 수 있는 크기의 공간이 연속적으로 나열되어 있음을 확인할 수 있다. 연속적으로 나열이 되어있다 보니 offset으로 계산할 수 있기 때문에 원하는 원소를 바로 조회할 수 있다.

확장 🌱

  • 조회 연산이 O(1)인 자료구조는 배열 밖에 없을까
  • 배열의 크기가 너무 커서 연속된 블럭으로 할당할 수 없을 경우 어떤 일이 발생할까
    • → Undefined Behavior (UB)
  • 배열의 offset은 어떻게 계산하는가 → 250518202725
  • 배열의 크기를 벗어나는 곳을 조회하면 어떻게 되는가
    • → Index Out of Bound Exception
    • → Undefined Behavior (UB)
  • 배열의 강점은 조회밖에 없나
  • 스크립트 언어의 배열은 어떻게 각기다른 종류의 타입을 담아낼 수 있는가 → 250518152200

관련 노트 📘

  • 250512043750 - 배열의 삽입과 삭제에는 O(n)의 시간이 필요하다
  • 250513192645 - 연결리스트의 조회는 순차적으로 이루어진다
  • 250514212107 - 조회, 삽입, 삭제 모든 부분에서 성능이 필요하다면 해시테이블을 고려해보자
Backlinks: