객체와 배열의 Big O 표기법

객체의 빅오

• 자바스크립트에서 객체의 keys-values 쌍은 index가 따로 없기 때문에 삽입, 제거, 탐색, 접근 등의 작업에 드는 시간이 arrays와 다르다.

객체의 내장 메서드 및 시간 복잡성

 const example = {
  key: value
}

객체의 O(1) 표기법

• 단순히 키를 가지고 삽입, 제거, 접근을 하는 것을 의미한다.
• Big O 표기법에서 객체는 데이터 삽입, 제거 및 접근( ex - 세 번째 요소 찾기 , 즉 정확히 요소를 알고 있기에 즉시 접근이 가능함. )에 유리하다. 이러 난 유형을 O(1)이라 표현한다.
• Big O 표기법에서 다음과 같은 접근법은 키를 기반으로 하기에 다른 키/값에 영향을 주지 않고 실행한다.
• hasOwnProperty 메서드는 O(1) 또는 상수의 시간을 가진다. 객체에 키가 있는지 여부에 따라 ture 또는 false를 반환하여 작동하기 때문이다.

객체의 O(N) 표기법

• Object.keys
• Object.values
• Object.entries
• 위의 세가지는 객체의 모든 항목을 찾아야 한다. 항목 수가 증가할수록 출력 시간이 증가하므로 O(N)이라 표기한다.

let foodStore = {
  firsName: 'Emart',
  costomer: true,
  numberOfemployee : 10,
  foodBrand: ['오리온','농심','해태']
}

Object.keys(foodStore)
출력 : [firsName,costomer,numberOfemployee,foodBrand]

Object.values(foodStore)
출력 : ['Emart', true, 10, ['오리온','농심','해태']]

Object.entries(foodStore)
출력 : [
['firsName', 'Emart'],
['costomer', true],
['numberOfemployee', 10],
['foodBrand', ['오리온', '농심', '해태']],
]

---

배열의 빅오

• 배열은 정렬된 데이터 구조이며, 모든 유형의 데이터를 저장하는데 사용된다.

배열의 내장 메서드 및 시간 복잡성

const array = ['a', {}, 10, [], false]

배열의 표기법

• Big O 표기법에서는 배열은 요소에 대한 빠른 접근이 필요할때 유리하다.
• 예로 들어 인덱스로 각 요소에 접근 할 때를 말한다.
• 2개 또는 2000개 요소가 있는 배열은 메서드 접근에서도 정확한 인덱스 번호를 안다면 시간 복잡도는 O(1)로 표기된다.
• 배열은 삽입, 제거 에서 시간 복잡도를 O(1) 또는 O(n)으로 표기할 수 있다.
• 차이점은 배열 요소가 삽입되거나 제거되는 위치에 의해 달라지는데, 요소가 배열의 끝에서 삽입되거나 제거되면 마지막 인덱스 요소만 영향을 받기 때문에 메서드는 O(1)로 나타낼 수 있다.
• 요소가 배열의 시작 부분에서 삽입되거나 제거되면 모든 요소가 영향을 받고 배열의 요소수에 따라 작업 수가 증가하므로 O(n) 표기법을 나타낸다.
• 배열의 검색 방법에는 O(n)이라 표기한다. 검색방법은 배열 의 모든 요소를 확인하기 때문이다.

배열의 메서드들

• 배열에는 다양한 메서드들이 있다.
• push, pop, shift, unshift, concat, slice, splice, sort, map

배열 메서드 O(1) 표현식

• push, pop 은 배열의 끝에서 요소를 추가하거나 제거하는 작업이 포함.

배열 메서드 O(n) 표현식

• shift, unshift는 배열의 시작 부분에서 추가하거나 제거하는 것, 실행시간은 배열의 모든 인덱스에 영향을 미치기 때문에 입력 또는 O(n)과 함께 증가한다.
• concat 은 두개 이상의 배열을 새 배열로 결합하는 데 사용한다. 결합 시에 배열의 입력 수가 증가함에 따라 선형 방식으로 런타임도 증가한다.
• slice는 배열의 복사본을 만드는 것과 관련 있다. 입력에 따라 런타임 증가한다.
• splice는 기존 요소를 제거하거나 새 요소를 추가하여 배열의 내용을 변경한다. 모든 배열 입력이 영향을 받기 때문에 런타임이 길다.
• map 은 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환한다. 배열의 모든 요소와 적어도 한 번은 상호작용해야 한다는 사실로 런타임에 영향을 미친다.

O(n * log n) 표현식

• 정렬 방법에는 O(n) 보다 나쁜 O(n * log n)이 있다.
• 요소 간의 비교가 필요하고 요소를 두 번 이상 방문 해야 하기 때문이다.

 

 

 

 

🚀 틀린점이 있어 지적할 사항이 있다면, 피드백해주시면 감사하겠습니다. 😊