[알고리즘] Big O of Objects & Arrays
객체와 배열이 Big O 관점에서 어떻게 동작하는지 이해하기
Objects (=Unordered collections)
객체의 가장 큰 특징은 순서가 없고 키-값 쌍으로 데이터를 저장한다는 것이다. 각 데이터 항목은 고유한 키를 가지며, 이 키를 통해 값에 접근할 수 있다.
When to use objects
- 순서가 필요 없을 때
- 빠른 접근, 삽입, 삭제가 필요할 때
Big O of Objects
Insertion - O(1) : 객체에 새로운 키-값 쌍을 추가하는 작업은 상수 시간 안에 완료
Removal - O(1): 객체에서 특정 키를 제거하는 작업도 상수 시간 안에 완료
Searching - O(N): 객체에서 특정 값(value)을 찾는 작업은 최악의 경우 모든 키를 확인해야 하므로 선형 시간(O(N))이 걸릴 수 있다.
Access - O(1): 특정 키를 사용해 값을 접근하는 것은 상수 시간 안에 가능
중요 포인트!
객체는 배열과 달리 특정 위치(시작, 중간, 끝)에 데이터를 삽입할 수 없다. 대신, 객체는 키를 통해 데이터를 추가하며, 순서는 중요하지 않다. 따라서, 순서가 전혀 필요하지 않을 때, 객체는 훌륭한 선택이다!
Object Methods
Object.keys - O(N): 객체의 모든 키를 배열로 반환하는 이 메서드는 객체의 모든 키를 확인해야 하므로 선형 시간이 소요
Object.values - O(N): 객체의 모든 값을 배열로 반환하는 메서드로, 역시 선형 시간이 소요
Object.entries - O(N): 객체의 키-값 쌍을 배열로 반환하는 이 메서드도 선형 시간이 소요
hasOwnProperty - O(1): 특정 키가 객체에 존재하는지 확인하는 이 메서드는 상수 시간 안에 결과를 반환
Arrays(=Ordered lists)
배열의 가장 큰 특징은 정렬된 순서를 가진다는 것다. 그러나 연산은 시간이 오래 걸림
(= 배열의 각 요소는 고유한 인덱스를 가지고 있다)
When to use Arrays
- 순서가 중요한 데이터일 때
- 인덱스를 통한 빠른 접근(Access)이 필요할 때
- 데이터의 빈번한 추가/삭제가 끝에서 이루어질 때
- 비교적 적은 양의 데이터: 데이터가 많아지고 삽입, 삭제가 자주 발생하면 배열의 성능이 저하될 수 있다. 이러한 경우에는 다른 데이터 구조를 고려하는 것이 좋다.
Big O of Arrays
- Insertion - 어디에 추가하느냐에 따라 다름
- Removal - 어디에 삭제하느냐에 따라 다름
- 배열의 끝에 요소를 추가하거나 삭제하는 경우 O(1)
- 배열의 앞부분에 추가하거나 삭제하는 경우 O(N)
- Searching - O(N): 배열에서 특정 요소를 찾는 데는 최악의 경우 모든 요소를 확인해야 하므로 선형 시간(O(N))이 소요
- Access - O(1): 인덱스를 사용해 배열의 요소에 접근하는 것은 상수 시간 안에 가능
Array Methods
- 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/etc. - O(N): 배열의 각 요소에 대해 반복 작업을 수행하는 메서드들
마무리
객체는 순서가 필요 없는 데이터 관리와 빠른 접근이 중요한 상황에서 유리하며, 배열은 순서가 중요한 데이터 처리와 인덱스를 활용한 빠른 접근이 필요한 경우에 적합하다. 이 두 데이터 구조의 Big O 분석을 이해함으로써, 상황에 맞는 최적의 데이터 구조를 선택하고, 더 효율적인 코드를 작성할 수 있다