빅오 관점에서 객체와 배열은 어떻게 작동하는가?

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 강의를 기반으로 작성한 내용입니다.

객체 Object 

객체는 언제 사용해야할까?

• 데이터 정렬이 필요 없을 때(순서가 필요 없을 때)
• 데이터에 빠르게 접근하고 입력하고 제거할 때

객체의 시간복잡도(Big O of Object)

객체는 정렬되어있지 않고 시작과 끝이 없다고 할 수 있습니다. 그렇기 때문에 데이터가 늘어나도 해당 데이터에 접근하는 시간은 같습니다. 따라서 특정 키(key)에 접근(access)하는 시간은 일정합니다.

그러나 탐색(searching)의 경우는 앞서 말한 접근의 경우와는 다릅니다. 탐색은 키(key)안에 있는 특정 값(value)을 찾는 과정입니다. 탐색하고자 하는 값이 어떤 키에 있는지 알 수 없기 때문에 일반적으로 생각하면 객체 안에 들어있는 항목들을 들여다 보아야 하며 객체의 크기가 커지면 탐색의 시간 복잡도 또한 증가하는 것을 이해할 수 있습니다. 따라서 객체 자료에 대한 탐색(searching)의 시간 복잡도는 O(N)이 됩니다.

객체 자료의 시간복잡도를 빅오표기법으로 정리하면 다음과 같습니다.

• Insertion - O(1)
• Removal - O(1)
• Searching - O(N)
• Access - O(1)

객체 메서드의 시간복잡도(Big O of Object Methods)

객체 메소드의 시간복잡도를 살펴봅시다.

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

keys, values, entries 메서드의 경우는, 객체의 크기가 커지면 커진 크기 만큼 처리해야할 연산도 늘어나게 됩니다. 예를들어, 어떤 객체가 100개의 프로퍼티를 가지고 있다면 이 객체를 Object.keys 메서드를 사용하면 100개에 대해 연산을 해야합니다. 프로퍼티 개수가 증가하면서 처리해야할 연산의 개수도 비례하여 증가하겠죠? 따라서 해당 메서드들은 O(N)의 시간복잡도를 갖습니다.

 

반면, hasOwnProperty의 시간복잡도는 다른 메서드와 달리 O(1) 입니다. hasOwnProperty 메서드는 특정 키(key)의 존재 여부를 불리언(boolean) 값으로 반환하기 때문에 데이터가 아무리 많이 늘어나도 해당 메서드를 수행하는데 걸리는 시간은 동일합니다. 이는 앞서 객체 자료의 시간복잡도에서 살펴본것과 같이, 특정 키(key)에 대한 접근(access)이라 볼 수 있겠습니다.

object.hasOwnProperty O(1)의 시간복잡도 갖는 이유
 
객체의 속성 접근이 해시 테이블을 기반으로 이루어지기 때문입니다. 자바스크립트에서 객체는 내부적으로 해시 테이블과 유사한 구조를 사용하여 속성을 저장합니다. 이러한 구조는 객체의 속성 이름을 해시 테이블의 키로 사용하고, 해당 키에 대한 값(속성 값)을 빠르게 검색할 수 있게 해줍니다. 

 

요약 (Recap)

• 객체는 정렬이 되어있지 않아 순서가 없지만 대부분의 연산에서 시간 복잡도가 O(1) 이므로 데이터를 빠르게 처리할 수 있습니다.
• 탐색(searching)은 선형 O(N)의 시간복잡도를 갖습니다.

---

배열 Array

배열은 언제 사용할까?

• 정렬되어 있는 자료가 필요할 때
• 데이터에 대한 빠른 접근(access), 삽입(insertion), 삭제(removal)가 필요할 때

❗️정렬이 필요한 경우에는 유용하지만 배열 자료는 데이터 정보 뿐만 아니라 순서도 포함되어 있기 때문에 연산을 하는데 더 많은 시간이 걸릴 수 있다는 점을 참고합시다!

배열 메서드의 시간복잡도 Big O of Arrays

• Insertion - 상황에 따라 다름
• Removal - 상황에 따라 다름
• Searching - O(N)
• Access - O(1)

객체와 동일하게 데이터에 접근하는 연산은 O(1)의 시간복잡도를 갖습니다. 찾고자 하는 값의 유효한 인덱스를 알고 있다면 해당 데이터를 바로 찾을 수 있기때문입니다. 예를들어, 해당 인덱스가 유효한 9000번째 요소의 값을 찾는다면 O(1)의 시간복잡도로 연산을 처리할 수 있습니다. 배열 요소가 얼마나 많은지 상관없이 말이죠!

배열에 데이터를 추가하는 경우와 제거하는 경우에는 상황에 따라 다릅니다. 배열의 마지막에 추가 또는 삭제하는 경우에는 객체와 마찬가지로 마지막 인덱스에 해당 데이터를 추가 또는 제거하면 되기 때문에 배열의 길이와 상관없이 일정한 O(1)의 시간복잡도를 갖게됩니다.

하지만, 배열의 앞 또는 중간에 데이터를 추가할 경우, 추가 또는 제거가 되는 그 이후부터 데이터의 인덱스를 새롭게 배정해야하고 배열의 길이(데이터의 개수)만큼 추가 작업이 필요하기 때문에 이 경우에는 O(N)이 됩니다.

이를 구체적으로 살펴보자면 배열에서의 데이터 추가의 경우 두가지 연산이 일어나는데 데이터 삽입과 이동 입니다.

따라서 배열의 데이터 삽입은 O(1), 데이터를 이동시키는 것은 O(N) 이므로 결국 O(N)의 시간복잡도가 되는 것입니다.

Big O of 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)