배열과 오브젝트 성능 평가 - 1

the runtime for arrays and objects

목표

  • 빅오의 시점에서 오브젝트와 배열이 어떨게 작동되는지 확인
  • 배열 앞에 데이터를 추가하는것은 나쁜 것인지 확인
  • 내장 메소드뿐만 아니라 배열 및 객체에 대한 런타임을 비교하고 대조

객체의 빅오 (Big O)

빅오와 성능 보는 관점으로 확인한다.

Unordered, key value pairs
정렬되어있지 않는 데이터 구조로 모두 key value 짝을 갖고 저장되어 있다.

When to use objects

  • when you don’t need order
    객체는 정렬되어 있을 필요가 없을 때 잘 작동한다.
  • When your need fast access / insertion and removal
    빠른 접근, 입력과 제거를 원할 때 좋다. 정렬되어 있지는 않지만, 객체는 매우 빠르다.

Big O of Objects

Insertion - $O(1)$
Removal - $O(1)$
Searching - $O(N)$
Access - $O(1)$
When you don’t need any ordering, objects are an excellent choice.

입력, 제거, 접근하는 시간이 상수 시간이다.
어떠한 정보를 접근하는 시간 (어떤 특정한 정보다 어떤 값에 있는지 확인)
탐색은 선형 시간이다.

자바스크립트는 상수 시간 내에 정보를 객체 안에 저장할 수 있다.
원하는 내용을 상수 시간 내에 불러올 수 있다. 기본적인 연산은 정렬되어있지 않기 때문에 매우 빠르게 한다.
객체에 시작과 끝이 없으므로 어디에 새로운 객체를 입력하든지 상관없다.
(객체의 시작이나 중간, 끝에 넣을 수 있다.)

Objects Example 📝

  • Objects.js 코드 
    1
2
3
4
5

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

코드에 있는 객체 리터럴에는 instructor 라는 변수에 key value 3개를 저장한다.

  • fristName
  • isInstructor
  • favoriteNumber

ex) true 값이 이 객체에서 어디에 저장되어 있는 것인지 알아본다.

  • firstName 부터 확인한다.
  • isInstructor 도 확인한다. → true 값이 있다.

예시와 다르게 속성들이 많을 수록(N이 늘어날수록) 그만큼 걸리는 시간도 늘어난다.

Big O of Object Methods

객체들과 따라오는 메소드를 확인해본다.

Object.keys - $O(N)$
Object.values - $O(N)$
Object.entries - $O(N)$
hasOwnProperty - $O(1)$

key, value, entrie는 모두 $O(N)$ 선형 시간이다.

Example Method O(N) 📝

ex) Object.keys, Object.entries 메소드에 객체를 전달한다.
> Object.keys(instructor)
> Object.entries(instructor)

결과
> (3) [“firstName”, “isInstructor”, “favoriteNumbers”]
> (3) [Array(2), Array(2), Array(2)]

$O(N)$ 선형 시간은 아이템 갯수가 늘어나면서 각 아이템을 접근해서 이 배열에 추가해야하는 시간이 늘어난다.
(elements가 100개이거나 속성이 100개면 처리해야할 연산도 100개)

N에 따라 시간은 변동한다. 2N 이거나 50N 일 수 있다.
결국에는 $O(N)$ 으로 정리가 된다.

Example Method O(1) 📝

ex) hasOwnProperty 메소드에 속성을 전달한다.
> instructor.hasOwnProperty(“firstName”)

결과
> true

first 라는 속성이 있는지 없는지만 알려준다.

배열이 빠를 수도 있지만, 정렬되어 있어 작업에 따라 느릴 수 있다.
하지만 객체는 간단해서 어떤 상황에서도 빠르게 작동한다.

모든 연산, 입력, 접근, 업데이트, 제거 모두 상수 시간이다.
탐색은 희귀하지만, $O(N)$ 은 N에 다라서 자라기 때문에 선형 시간이다.

Example 오브젝트

  1. 오브젝트에 키와 값을 추가하기 위한 빅오는 무엇인가?
    ① $O(n)$
    ② $O(n)$
    ③ $O(n logn)$

    1번 정답

    답 : $O(1)$


  2. 오브젝트의 키에 접근하기 위한 빅오는 무엇인가?
    ① $O(1)$
    ② $O(n)$

    2번 정답

    답 : $O(1)$


  3. 오브젝트의 키를 제거하기 위한 빅오는 무엇인가?
    ① $O(1)$
    ② $O(n)$
    ③ $O(n^2)$

    3번 정답

    답 : $O(1)$


🌞 정보 : 공부 기록용 블로그입니다. 오타나 내용 오류가 있을 경우 알려주시면 감사하겠습니다.

댓글남기기

Recent posts