빅오 관점에서 객체와 배열이 어떻게 작동하고 그에 따른 성능을 어떻게 평가하는지 알아보자.
객체
객체는 key와 value를 가지고 있고 정렬되어있지 않은 데이터 구조이다. 데이터를 정렬할 필요가 없거나 빠르게 데이터에 접근해서 입력과 삭제를 원할 때 사용한다.
- 입력 : O(1)
객체에는 순서가 없어 입력할 때, 입력값이 들어갈 위치를 신경쓸 필요가 없다. 단순히 key를 사용해 데이터를 추가하기 때문에 아이템의 개수에 영향을 받지 않는다. - 제거 : O(1)
고유의 key를 사용해 제거가 필요한 아이템에 접근하기 때문에 아이템의 개수에 영향을 받지 않는다. - 탐색 : O(N)
모든 값을 확인해야 하기 때문에 값이 어디에 저장되어 있는지 탐색하는 시간은 아이템의 개수가 많아질수록 느리다. - 접근 : O(1)
고유의 key를 사용해 데이터에 접근해서 아이템의 개수에 영향을 받지 않는다.
객체의 메소드 성능
Object.keys: O(N)Object.values: O(N)Object.entries: O(N)
아이템의 개수가 많아지면 각 아이템에 접근해 반환할 배열에 요소로 추가하는 작업이 늘어난다.Object.hasOwnProperty: O(1)
key로 접근하기 때문에 아이템 개수에 영향을 받지 않는다.
배열
특정한 기준으로 정렬되어 있고 요소마다 인덱스를 가진다. 데이터의 정렬이 필요할 때 사용하며 객체에 비해 입력과 제거를 할 때 성능이 떨어진다.
- 입력 : 끝에 추가한다면 O(1), 앞에 추가한다면 O(N)
인덱스가 하나씩 밀리기 때문에 새로 배정해야 한다. - 제거 : 끝 요소를 제거한다면 O(1), 첫 요소를 제거한다면 O(N)
마찬가지로 인덱스를 다시 배정해야 한다. - 탐색 : O(N)
배열의 길이가 길어질수록 탐색 시간은 길어진다. - 접근 : O(1)
인덱스로 접근하기 때문에 배열의 길이에 영향을 받지 않는다.
배열의 메소드 성능
Array.push: O(1)Array.pop: O(1)Array.shift: O(N)Array.unshift: O(N)Array.concat: O(N)Array.slice: O(N)Array.splice: O(N)Array.sort: O(N * log N)Array.forEach / map / filter / reduce...: O(N)
요소마다 작업을 해야하기 때문에 배열의 길이가 늘어날수록 실행 시간도 늘어난다.
✍️ <JavaScript 알고리즘 & 자료구조 마스터클래스> 강의를 들으며 알게 된 내용을 정리하였습니다.
