[UJAD] 배열과 오브젝트의 성능 평가

Objects Big O

[!IMPORTANT]

자바스크립트에서 객체(Object)의 삽입, 제거, 조회, 검색 등의 주요 연산과 관련 메서드들의 시간복잡도는 대부분 O(1)이다. 이는 객체가 해시 테이블을 기반으로 구현되었기 때문이다.

When to use objects

• When you don't need order
• When you need fast access or insertion and removal

Big O of objects

Insertion: keys and values - O(1)
자바스크립트 객체는 해시 테이블을 기반으로 동작하므로, 키를 해시 함수에 전달해 해당 키의 위치를 계산하고 값을 저장한다. 해시 충돌이 적은 경우 삽입은 상수 시간에 이루어진다.

Remove: keys and values - O(1)
객체의 키를 삭제할 때도 해시 테이블을 이용해 해당 위치를 빠르게 찾아 삭제하므로 상수 시간에 처리된다. 내부적으로는 delete 키워드를 사용해 해당 키와 값을 제거한다.

Searching: value - O(N)
특정 키를 이용해 값을 조회할 때, 해시 테이블의 인덱스를 계산하고 값을 반환하므로 상수 시간에 수행된다.

Access: key - O(1)
객체는 키를 기준으로 동작하는 자료구조이기 때문에 값을 기준으로 검색하려면 객체의 모든 키-값 쌍을 순회해야 한다. 따라서 검색은 객체 크기 ( n )에 비례하는 선형 시간이 소요된다.

Why searching is O(N)?

let instructor = {
  firstName: "Kelly",
  isInstructor: true,
  favoriteNumbers: [1, 2, 3, 4]
}

Big O of Object Methods

Object.keys - O(N)
객체의 모든 키를 순회하여 배열로 반환하므로 객체 크기에 따라 선형 시간이 소요된다.

Object.values - O(N)
모든 키-값 쌍을 순회하여 값만 배열로 반환하므로 선형 시간이다.

Object.entries - O(N)
모든 키-값 쌍을 순회하여 [key, value] 쌍의 배열을 생성하므로 선형 시간이 걸린다.

hasOwnProperty - O(1)
특정 키가 객체의 고유 속성인지 확인하기 위해 단일 키의 존재 여부만 검사하므로 상수 시간에 수행된다.

Arrays Big O

[!IMPORTANT]

자바스크립트에서 배열은 동적 배열로 구현되어 있으며, 특정 연산의 시간복잡도는 배열의 크기 (n)에 따라 달라질 수 있다. 배열은 인덱스 기반 접근이 가능하다는 점에서 일부 연산은 빠르게 수행되지만, 요소의 위치에 따라 시간이 달라질 수 있다.

When to use Arrays

• When you need order
• When you need fast access/insertion/removal (sort of)

Big O of Arrays

Insertion - depends

• 배열 끝에 삽입하는 경우(push)는 새 요소를 추가하는 데 상수 시간 O(1)이 걸린다.
• 중간이나 앞에 삽입(unshift, splice)할 경우, 이후의 모든 요소를 한 칸씩 이동해야 하므로 배열 크기에 비례하는 선형 시간 O(n)이 소요된다.

Removal - depends

• 끝에서 제거(pop)는 상수 시간 O(1)에 수행된다.
• 중간이나 앞에서 제거(shift, splice)할 경우, 이후의 모든 요소를 한 칸씩 이동해야 하므로 선형 시간 O(n)이 걸린다.

Searching - O(N)
배열에서 특정 값을 찾으려면 배열의 모든 요소를 순회해야 하므로 선형 시간이 걸린다.

Access - O(1)
배열은 인덱스 기반 자료구조이므로 특정 인덱스에 접근하는 데 상수 시간이 걸린다.

[!NOTE]

검색(Search)와 조회(Access)의 차이

• 조회: 내가 찾으려는 값이 어디 있는지 위치(인덱스나 키)를 알고 있을 때
  ex) arr[2], obj['key']

• 검색: 내가 찾으려는 값은 알고 있지만, 그 값이 어디 있는지 모를 때
  ex) arr.includes(42), Object.values(obj).includes('value')

Why Insertion and Removal Depends?

if we insert/remove at the beginning of the array, we have to re-index other elements. So it is O(N).

it is not 'efficient' to insert/remove from the beginning.

Big O of Array Operations

push - O(1)
배열 끝에 요소를 추가하므로 추가 작업 없이 상수 시간에 수행된다.

pop - O(1)
배열 끝에서 요소를 제거하므로 추가 작업 없이 상수 시간에 수행된다.

shift - O(N)
배열의 첫 번째 요소를 제거하고 나머지 요소를 모두 앞으로 이동해야 하므로 선형 시간이 걸린다.

unshift - O(N)
배열의 앞에 새 요소를 추가하고 나머지 요소를 모두 뒤로 이동해야 하므로 선형 시간이 걸린다.

concat - O(N) / O(n + m) (두 배열의 길이가 각각 (n)과 (m)일 때)
새 배열을 생성하고, 기존 배열의 요소를 모두 복사해야 하므로 두 배열의 길이에 비례하는 시간이 걸린다.

slice - O(N) / O(k) ((k)는 복사된 요소의 수)
지정된 범위의 요소를 복사하여 새 배열을 반환하므로 범위 내 요소의 수에 비례하는 시간이 소요된다.

splice - O(N)

• 요소를 삽입하거나 삭제한 후, 배열의 나머지 요소를 이동해야 하므로 선형 시간이 걸린다.
• 영향을 받는 요소의 개수에 따라 시간이 결정된다.

sort - O(N * log N)
자바스크립트는 최적화된 정렬 알고리즘(예: Timsort)을 사용하며, 이는 평균적으로 (O(n \log n))의 시간복잡도를 가진다.

forEach/map/filter/reduce etc. - O(N)

• forEach
  • 배열의 모든 요소를 순회하여 콜백을 실행하므로 배열 크기에 비례한다.
• map
  • 배열의 모든 요소를 순회하며 콜백을 실행하고 새 배열을 생성하므로 배열 크기에 비례한다.
• filter
  • 배열의 모든 요소를 순회하며 조건에 따라 새 배열에 요소를 추가하므로 배열 크기에 비례한다.
• reduce
  • 배열의 모든 요소를 순회하며 누적 작업을 수행하므로 배열 크기에 비례한다.