performance of array & object

object

객체는 순서(unordered)가 없고, key - value 쌍으로 이루어진 데이터의 집합이다. 따라서 순서에 관계 없는 데이터를 보관할 때 사용하면 좋다. 뿐만 아니라, 빠르게 데이터에 접근하거나 데이터를 추가/삭제 할 때에도 유용하다. 이 때 빠르다는 것은 상수의 시간 복잡도(O of constants)를 갖는다는 것을 의미한다. 

 

let harry = {
  fullName: 'harry styles',
  age: 28,
  favoriteNumbers: [1, 2, 3, 4],
}

 

1. insertion => O(1)
2. removal => O(1)
3. access => key를 이용해 value에 접근하는 것을 의미, O(1)
4. searching => 어떤 value가 객체에 존재하는지 확인하는 것을 의미(indexOf) O(n)

 

js의 객체 내장 메서드에서도 시간 복잡도를 확인해 볼 수 있다. 

 

1. Object.keys(obj), values, entries => O(n)
2. obj.hasOwnProperty("key") => 전달한 key를  프로퍼티로 가지고 있는지 아닌지를 boolean으로 반환, O(1)
   • harry.hasOwnProperty("fullName")을 예로 들어 보자. 만약 harry.fullName에 접근할 수 있는지, 아닌지를 가지고 해당 프로퍼티가 있는지, 없는지를 확인할 수 있기 때문에 시간 복잡도는 O(1)이 된다. 

array

배열은 순서가 있는 데이터의 집합이다. 따라서 어떤 데이터를 순서대로 정렬해야 할 때 사용할 수 있다(유일한 방법은 아니다). 배열의 값에 접근하는 것, 어떤 값이 존재하는지 검색하는 것은 객체의 경우와 같은 시간 복잡도를 갖지만, 값을 추가/삭제 하는 데에 있어서는 더 낮은 성능을 갖는다. 

 

let singers = ["harry", "taylor", "lana", "olivia"]

 

1. insertion => "어디에" 값을 추가하냐에 따라 시간 복잡도가 다르다. 
   • 배열의 꼬리에 아이템을 추가 => O(1)
   • 배열의 머리에 아이템을 추가 => 모든 아이템의 index가 바뀌어야 하므로 => O(n)
2. removal => insertion과 마찬가지로 "어디에" 있는 값을 삭제하느냐에 따라 시간 복잡도가 다르다. 
3. access => index를 이용해서 배열의 아이템에 접근하는 것을 의미, O(1)
4. searching =>  O(n)

 

js의 배열 내장 메서드에서도 시간 복잡도를 확인해 볼 수 있다. 대부분의 메서드가 O(n)의 시간 복잡도를 갖는 것을 알 수 있다. 

 

1. push, pop => O(1)
2. shift, unshift => O(n)
3. slice, splice, concat  => O(n)
   • slice(start, end) => start ~ end 인덱스의 아이템으로 이루어진 배열을 반환
   • splice(start, deleteCount, contents) => splice는 접착이라는 뜻을 가지고 있으며, start 인덱스 자리에서 deleteCount 만큼의 아이템을 삭제한 뒤, contents 아이템을 추가한다. 
   • concat => 여러 배열의 아이템들을 하나의 배열의 아이템으로 합친 뒤, 그 배열을 반환
4. forEach, map, filter, reduce... => O(n)
5. sort => O(N * log N)