Javascript에서 배열과 오브젝트의 빅오 (Big - O)

Javascript에서 배열과 객체는 자주 사용되는 데이터 구조입니다. 이 글에서는 배열과 객체의 성능을 빅오 표기법(Big O Notation)을 통해 비교하고, 배열의 시작 부분에 요소를 추가하는데 비용이 많이 드는 이유와 내장 메서드의 런타임 성능을 분석합니다.

 

객체의 빅오 표기법

객체는 정렬되지 않은 데이터 구조로, key-value 쌍으로 저장됩니다. 객체는 정렬이 필요 없을 때, 빠른 접근, 입력, 제거를 원할 때 유용합니다.

객체의 빅오

• 삽입: O(1)
• 삭제: O(1)
• 탐색: O(N)
• 접근: O(1)

내장 메서드의 빅오

• Object.keys: O(N)
• Object.values: O(N)
• Object.entries: O(N)
• hasOwnProperty: O(1)

배열의 빅오 표기법

배열은 정렬된 데이터 구조로, 특정 위치에 요소를 추가하거나 제거할 때 성능 차이가 발생합니다.

 

배열의 빅오

• 삽입:
  • 끝에 추가하면 O(1)
  • 앞에 추가하면 O(N) (모든 인덱스를 재정렬해야 하기 때문)
• 삭제:
  • 끝에 추가하면 O(1)
  • 앞을 삭제하면 O(N) (모든 인덱스를 재정렬해야 하기 때문)
• 탐색: O(N)
• 접근: O(1)

내장 메서드의 빅오

• push: O(1)
• pop: O(1)
• shift: O(N)
• unshift: O(N)
• concat: O(N)
• slice: O(N)
• splice: O(N)
• sort: O(N * log N)
• forEach/map/filter/reduce: O(N)

배열의 시작 부분에 요소를 추가하거나 제거하는 작업은 배열의 모든 요소를 이동시켜야 하므로 O(N)의 시간이 소요됩니다. 반면, 배열의 끝에 요소를 추가하거나 제거하는 작업은 O(1)로 더 효율적입니다. 따라서, 비어있는 배열을 제외하고는 push()와 pop()이 shift()와 unshift()보다 항상 빠릅니다.