[알고리즘] 객체와 배열의 Big O

blueprint-12 2022. 4. 14. 16:37

🍕객체(Object) ?

unordered, key value pairs

let instructor = {
  firstName: "cong",
  isInsructor: true,
  favoriteNumbers: [1, 2, 3, 4],
};

🍕객체(Obj)는 언제 이용하면 좋을까?

순서(order)가 필요없을 때 (when you don't need order) // 객체는 정렬되지 않은 데이터 구조를 가지고 있다. + key : value 페어로
빠른 접근, 입력과 제거를 원할 때( need fast access/ insertion and removal) -> Big O에서 빠르다고 했을 때, 입력, 제거, 접근하는 시간이 상수 시간 , O(1) 이라는 것을 의미

🍕객체(Obj)의 Big O

입력(Insertion) - O(1) 상수 시간 (*constant time)
제거(removal) - O(1) 상수 시간
탐색(Searching) - O(n) 선형 시간(*linear time) // 탐색의 경우는, 객체의 프로퍼티를 전부 순회해서 값을 확인해야하기 때문에 O(n)의 시간이 걸린다.
접근(Access) - O(1) 상수 시간

-> 객체의 모든 연산, 입력, 접근, 업데이트, 제거 모두 상수 시간(O(1))이다. 단, 탐색은 O(n)으로 선형 시간이다.

🍕객체(Obj) 메소드의 Big O

Object.keys() - O(n)
Object.values() - O(n)
Object.entries() - O(n)
hasOwnProperty() - O(1)

-> 객체가 커질수록 객체 안에 저장되어 있던 데이터를 다루는 keys, values, entries와 같은 메소드도 있다.

-> hasOwnProperty()의 경우, 인수로 해당 프로퍼티 key를 받기 때문에 상수 시간이다.

결론: 객체의 빅오를 보면 굉장히 좋은 성능을 가지고 있음을 알 수 있다.

배열을 빅오를 통해서 판단해보고 객체와 비교했을 때 성능이 어떤지 확인해보자.

🍕배열(Array)

-orderd list

배열의 가장 중요한 점은 정렬되어있다는 점 -> 데이터가 정렬되어 있는 기준이 있음, 그냥 한 뭉치로 있는 객체와 다름

-정렬되어 있는 것이 필요하다면 유용하지만, 연산하는 시간이 더 걸릴 수 있다(단점).

// arrays (ordered lists)
let names = ['Michael', 'Melissa', 'Anya'];
//여러 데이터 타입을 담을 수 있다. 
//엘리먼트마다 붙어있는 index가 있다. 
let value = [true, {}, [], 2, 'awesome']; 
// 정렬되어 있는 데이터 구조가 배열만 있는 것은 아니다. 
// 자바스크립트에 그냥 내장되어 있는 구조일 뿐

🍕배열을 언제 쓰나요?

- 순서가 있어야 할 때

- when you need fast access/ insertion and removal( sort of..)

배열에서 데이터를 접근하는 것은 매우 빠르다.

🍕배열의 Big O

입력(Insertion) - it depends ..
- item을 추가할 때, 어느 위치냐에 따라서 달라집니다. 맨 뒤에 추가하는 경우는 O(1) 상수 시간입니다.
- 하지만, 맨 앞에 추가하게 되면 모든 item들의 index가 밀리기 때문에 각각의 엘리먼트마다 연산이 필요하게 되고 O(n) 선형 시간이 됩니다.
제거(removal) - it depends ..
- item을 제거하는 것도 입력과 마찬가지로 위치에 영향을 받습니다. 같은 이유로 맨 앞에서의 item제거는 O(n)으로 선형시간이 되고 뒤에서의 삭제는 O(1)으로 상수 시간입니다.
- 그런 이유로 비어있는 배열일 때만 제외하면, push와 pop 작업이 shift와 unshift보다 작업이 빠릅니다.
탐색(Searching) - O(n) 선형 시간(*linear time)
접근(Access) - O(1) 상수 시간 // 접근은 '객체'와 같이 상수 시간

배열에서 접근(Access)은 해당 값이 유효하기만하면 위치나 배열의 크기와 상관없이 (처음부터 끝까지 탐색하지 않음) 바로 찾을 수 있기 때문에 상수 시간입니다.

🍕배열 메소드의 Big O

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) // 배열을 정렬하는 것은 O(n)보다 시간이 더 걸린다. n*log n > O(n)
- 비교를하고 엘리먼트를 움직여야하며 정렬하려면 엘리먼트마다 한번씩 보는 것만으로 충분하지 않다.
- 해당 리스트 중에서는 sort가 가장 성능적으로 느리다.
forEach/map/filter/reduce/etc... - O(n) , 각각의 엘리먼트마다 작업을 실행하므로 배열이 커질수록 걸리는 시간도 늘어난다.

-> 대부분의 배열 관련 내장 메소드는 O(n)으로 선형 타임이다. 배열에서 O(n)을 간단하게 설명하면 엘리먼트마다 한 가지 작업을 실행한다고 생각하면 된다.