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

해당 글은 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)이라 볼 수 있겠습니다.

 

요약 (Recap)

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

 

---

 

배열 Array

배열은 언제 사용할까?

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

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

 

Big O of Arrays

배열의 시간복잡도를 알아보겠습니다.

• Insertion - It depends..
• Removal - It depends..
• Searching - O(N)
• Access - O(1)

객체와 동일하게 데이터에 접근하는 연산은 O(1)의 시간복잡도를 갖는다 즉, 찾고자 하는 값의 유효한 인덱스를 알고 있다면 해당 데이터를 바로 찾을 수 있다

 

예를들어, 해당 인덱스가 유효한 9000번째 요소의 값을 찾는다면 O(1)의 시간복잡도로 연산을 처리할 수 있다 배열 요소가 얼마나 많은지 상관없이 말이다

 

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

 

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

 

구체적으로 말하자면 배열에서의 데이터의 추가의 경우 두가지 연산이 일어나는데 데이터를 삽입하는 것과 이동시키는 것이다

 

따라서 배열의 데이터 삽입은 O(1)의 시간복잡도를 데이터를 이동시키는 것은 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)