1.2Analyzing Performance of Arrays and Objects

JavaScript 객체(Objects)

JavaScript의 객체는 순서가 없는 키-값 쌍의 집합이다.

javascript
const post ={
  category: 'algorithm',
  title: 'Analyzing Performance of Arrays of Objects',
  content: '...',
  // ...
}

객체는 순서가 중요하지 않고, 데이터에 빠르게 접근하거나 추가, 제거할 필요가 있을 때 사용한다. 일반적으로 JavaScript의 객체에 데이터 접근, 추가, 제거는 모두 O(1)의 시간 복잡도를 가진다.

다만, 데이터 검색은 다르다. 예를 들어 특정 값을 가진 키를 찾으려면 전체를 훑어야 하므로 O(n)이 걸린다.

객체에 쓰이는 메소드들의 시간 복잡도는 아래와 같다:

JavaScript 배열(Arrays)

JavaScript의 배열은 순서가 있는 값들의 집합이다.

javascript
const posts = ['Algorithm', 'PostgreSQL', 'TypeScript']

JavaScript의 배열에 있는 데이터에 접근하는 것은 O(n)이 아니라 O(1)이다. 즉, 첫 번째 요소든 마지막 요소든 접근 속도는 동일하다.

javascript
// 요소가 몇 번째에 있건간에 접근하는 시간은 완전히 동일하다.
console.log(posts[0]);
console.log(posts[3]);

배열에 요소를 추가하거나 제거할 때 배열은 순서를 유지해야 하므로, 앞쪽에서 데이터를 추가하거나 제거할 경우 나머지 요소들의 인덱스를 전부 이동시켜야 한다. 이로 인해 O(n)의 시간 복잡도를 가진다. 반면, 끝에 데이터를 추가하거나 제거할 경우 그냥 O(1)이다.

• 끝에 추가 (push): O(1)
• 끝에서 제거 (pop): O(1)
• 앞에 추가 (unshift): O(n)
• 앞에서 제거 (shift): O(n)

데이터 검색은 객체와 동일하게 O(n)이다.

배열에 쓰이는 메소드들의 시간 복잡도는 아래와 같다:

• Array.push: 배열 끝에 요소를 추가하고 새로운 길이를 반환, O(1)
• Array.pop: 배열 끝의 요소를 제거하고 그 값을 반환, O(1)
• Array.shift: 배열 앞의 요소를 제거하고 그 값을 반환, O(n)
• Array.unshift: 배열 앞에 요소를 추가하고 새로운 길이를 반환, O(n)
• Array.concat: 두 배열을 이어붙여 새로운 배열을 반환, O(n)
• Array.slice: 지정한 범위의 요소를 잘라 새로운 배열로 반환, O(n)
• Array.splice: 배열의 요소를 추가하거나 제거하여 원본 배열을 변경, O(n)
• Array.sort: 배열의 요소를 정렬하며, 원본 배열을 변경, O(n * log n)
• Array.forEach: 배열의 각 요소에 대해 콜백 함수를 실행(반환 없음), O(n)
• Array.map: 배열의 각 요소를 변형하여 새로운 배열을 반환, O(n)
• Array.filter: 조건을 만족하는 요소만 모아 새로운 배열을 반환, O(n)
• Array.reduce: 배열의 각 요소를 누적하여 하나의 결과값을 반환, O(n)