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

🍕객체(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)을 간단하게 설명하면 엘리먼트마다 한 가지 작업을 실행한다고 생각하면 된다.