[Algorithm] Object & Array

🍒 [230323 TIL] JavaScript Algorithms and Data Structures Masterclass

Object & Array

Big O of object

객체를 사용하기 좋을 때는 다음과 같다.

1. 정렬할 필요가 없을 때
2. 빠른 접근 / 삽입 / 삭제가 필요할 때

객체의 Big O
탐색 - O(N)
삽입 - O(1)
삭제 - O(1)
접근 - O(1)

 

탐색이 O(N)을 따르는 이유는 특정한 정보가 어떤 값에 있는지 확인하기 때문이다.

const information = {
    name: 'Shoupeach',
    isApeach: true,
    favoriteNumbers: [4, 8]
};

information이란 객체가 존재할 때 여기서 true라는 값이 information에서 어디에 저장되어 있는지 알기 위해서 먼저 name을 확인하고 값을 확인한다.

name의 값은 Shoupeach이기 때문에 통과한 뒤 isApeach를 확인하고 값을 확인한다.

isApeach의 값은 true이기 때문에 종료된다.

 

지금은 객체 안에 key-value 쌍이 3개 밖에 없지만, 객체 내부에 속성이 많을수록 (N이 커질수록) 확인해야 하는 key가 많아지기 때문에 O(N)을 따르게 된다.

 

Big O of object methods

객체 메소드의 Big O
hasOwnProperty - O(1)
Object.keys - O(N)
Object.values - O(N)
Object.entries - O(N)

Object.keys

Object.keys(information);
// ["name", "isApeach", "favoriteNumbers"]

Object.keys는 key가 들어있는 배열을 반환한다.

key가 늘어날수록 (N이 커질수록) 각 key들에 접근해서 배열에 추가해야하기 때문에 O(N)을 따른다.

 

Object.values

Object.values(information);
// ["Shoupeach", true, [4, 8]];

Object.values도 마찬가지로 N이 커질수록 반환되는 배열의 길이가 선형적으로 늘어나므로 O(N)을 따른다.

 

Object.entries(information);
// [["name", "Shoupeach"], ["isApeach", true], ["favoriteNumbers", [4, 8]]

Object.entries도 마찬가지로 N이 커질수록 반환되는 배열의 길이가 선형적으로 늘어나므로 O(N)을 따른다.

 

hasOwnProperty

information.hasOwnProperty("name");
// true

hasOwnProperty는 위 메소드들과는 다르게 접근의 개념이기 때문에 O(1)을 따른다.

 

Big O of array

배열은 객체와는 다르게 데이터가 정렬되어 있다.

정렬되어 있기 때문에 연산을 하는데 시간이 더 걸릴 수 있다. 🫠

 

배열을 사용하기 좋은 경우는 다음과 같다.

1. 데이터를 정렬할 때
2. 빠른 접근이 필요할 때

배열의 Big O
접근 - O(1)
탐색 - O(N)
삽입 - 삽입 위치에 따라 다름
삭제 - 삭제 위치에 따라 다름

JavaScript가 배열에 접근할 때, 요소가 10000개 있는 배열이 있다고 가정하고 arr[9000]을 호출하면 0부터 9000까지의 모든 인덱스를 탐색하는 것이 아니다.

9000번의 인덱스에 바로 접근할 수 있기 때문에 접근은 O(1)을 따른다.

 

Insertion

const names = ["Shoupeach", "Rabbit", "Ogu"];

names 배열 끝에 Namazuo라는 이름을 넣고 싶다면 push를 하면 된다.

push는 배열 끝에 추가하고 인덱스를 주는 것이기 때문에 객체에 새로운 key-value 쌍을 추가하는 것과 같아 O(1)을 따른다.

 

Namazuo를 배열의 맨 앞에 추가하게 되면 기존에 있던 요소들의 인덱스가 달라져버린다.

배열에 있는 요소마다 새로운 인덱스를 배정해줘야 하기 때문에 배열의 요소가 많을수록 (N이 커질수록) 작업량도 많아진다.

따라서 unshift는 O(N)을 따른다.

 

removal

배열의 요소를 삭제하는 것도 삽입의 경우와 같다.

names 배열 끝에 삽입한 Namazuo를 삭제하고 싶다면 pop을 하면 된다.

pop은 끝에 추가한 요소와 인덱스를 없애면 되기 때문에 O(1)을 따른다.

 

맨 앞에 추가한 Namazuo를 없애게 되면 unshift와 마찬가지로 배열에 남아있는 요소들의 인덱스가 달라진다.

N이 커질수록 인덱스를 수정하는 작업량도 많아지기 때문에 shift 또한 O(N)을 따른다.

 

빈 배열에 push, pop / unshift, shift를 하는 경우
배열이 비어있는데 맨 앞과 맨 뒤에 추가하거나 없애는 것은 똑같기 때문에 O(1)을 따른다.

 

Big O of array methods

배열 메소드의 Big O
~ 전부 암기할 필요는 없다 😵 ~
push - O(1)
pop - O(1)
unshift - O(N)
shift - O(N)
concat - O(N)
slice - O(N)
splice - O(N)
sort - O(N㏒N)
forEach / map / filter / reduce / etc. - O(N)

 

concat

const arr1 = ['a', 'b', 'c'];
const arr2 = ['d', 'e', 'f', 'g'];

arr1.concat(arr2);
// ["a", "b", "c", "d", "e", "f", "g"]

N개의 요소가 있는 배열에 M개의 요소가 있는 배열을 결합하는 것이기 때문에 O(N+M)인데 단순화 하면 결국 O(N)이다.

 

slice & splice

const animals = ['rabbit', 'ogu', 'elephant', 'hippo'];

animals.slice(2);
// ["elephant", "hippo"]
animals.splice(1, 0, 'dolphin');
// ["rabbit", "dolphin", "ogu", "elephant", "hippo"]

slice는 배열을 복사하는 메소드로 복사를 하고자 하는 요소가 늘어남에 따라 (N이 커질수록) 시간이 증가하기 때문에 O(N)을 따른다.

splice는 unshift와 shift처럼 기존 배열의 인덱스를 변경해야하기 때문에 O(N)을 따른다.

 

sort

animals.sort();
// ["elephant", "hippo", "ogu", "rabbit"]

sort는 비교도 해야하고 요소의 이동도 필요하다.

일단 알아야 할 것은 배열을 정렬하는 것이 O(N)보다는 크다는 사실이다.

sort는 O(N㏒N)을 따른다.

 

etc

그 외 배열로 할 수 있는 대부분의 메소드는 O(N)을 따른다.

배열의 요소를 전부 지나치면서 작업을 할 때 for문을 사용하는 것을 생각하면 O(N)인 이유를 금방 파악할 수 있을 것 같다..😉