이전글
베열과 오브젝트 성능 평가 in JS - 1
베열과 오브젝트 성능 평가 in JS - 2

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

📁 Big O of Array Operations

Array Operations Big O
push $O(1)$
push $O(1)$
shift $O(N)$
unshift $O(N)$
concat $O(N)$
slice $O(N)$
splice $O(N)$
sort $O(N*logN)$
forEach / map / filter
/ reduce / etc.		 $O(N)$

Array.push(), Array.pop()

push 와 pop 작업은 상수 시간 $O(1)$ 이다.
배열 맨 끝에 추가하고 제거하는 작업은 배열의 크기와 상관 없다.

반면에 shift 와 unshift 는 전부 인덱스를 다시 정해줘야 하기 때문에 번거롭다.
엘리먼트의 갯수가 늘어나면 인덱스를 정리해야할 갯수도 늘어난다.
그러니 선형 시간 $O(N)$ 이다.

Array.concat()

concat, slice, splice 도 전부 선형 시간 $O(N)$ 이다.
concat 은 여러 배열을 합쳐준다.

  • ex) Array.concat() 코드 
    1
2
3
4
5

      var array1 = ['a', 'b', 'c'];
  var array2 = ['d', 'e', 'f'];

  console.log(array.concat(array2));
  //expected output: Array ['a', 'b', 'c', 'd', 'e', 'f']

    $O(N)$ 이라고 하면 배열 하나에 있는 엘리먼트 N 갯수에 적용하는 작업이라고 생각할 수 있다.
    그런데 배열이 두 개가 되어 또 있는 배열의 크기가 M이면 걸리는 시간이 사실상 $O(N+M)$ 이고 사실상 $O(N)$ 으로 표현해도 충분하다.
    결국 결합할 배열이 커질수록, 끝에 붙일 배열의 크기만큼 시간도 그만큼 늘어나기 때문이다.

Array.slice()

slice 는 배열 일부나 전체를 가져올 수 있다.

  • ex) Array.slice() 코드 
    1
2
3
4
5
6
7
8
9
10
11

      var animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];
              //   0       1        2        3        4

  console.log(animals.slice(2));
  //expected output: Array ['camel', 'duck', 'elephant']

  console.log(animals.slice(2, 4));
  //expected output: Array ['camel', 'duck']

  console.log(animals.slice(1, 5));
  //expected output: Array ['bison', 'camel', 'duck', 'elephant']

    여기서의 작업은 얼마나 많은 갯수를 복사하는지 중요하다.
    만약 10개를 복사하는 것과 100개를 복사하는 것을 비교했을 때 걸리는 시간이 복사하는 엘리먼트 갯수만큼 늘어나는 $O(N)$ 인 것이다.

Array.splice()

splice 는 지정한 인덱스 위치에 엘리먼트를 제거하고 추가하거나 교체할 수 있다.

  • ex) Array.splice() 코드 
    1
2
3
4
5
6
7
8
9
10

      var months = ['Jan', 'March', 'April', 'June'];
  monthe.splice(1, 0, 'Feb');
  //inserts at 1st index position
  console.log(months);
  //expected output: Array ['Jan', 'Fed', 'March', 'April', 'June']

  monthe.splice(4, 1, 'May');
  //replaces 1 element at 4th index
  console.log(months);
  //expected output: Array ['Jan', 'Fed', 'March', 'April', 'June', 'May']

    배열 중간에 엘리먼트를 추가한다면 단순히 $O(N)$ 으로 표현한다.
    중간에 추가하면 shift 를 해서 뒤에 있는 인덱스를 다시 정리해야 한다.
    일반적으로 배열과 관련된 작업들은 $O(N)$ 으로 표시한다.

sort, forEach…

배열을 정렬하는 것은 $O(N)$ 보다는 더 크다 sort 메소드가 $O(N*logN)$ 으로 여기서 가장 느리다.
엘리먼트를 비교하고 이동시키면서 정렬하려면 엘리먼트들을 한 번 이상 보게 되기 때문이다.

forEach, map, filter, reduce, etc. 는 모두 $O(N)$ 이다.
엘리먼트마다 한 가지 작업을 실행하고, 갯수를 기록허거나 boolaen 으로 확인하고, 출력을 할 수 있다.
어떤 작업을 하든 엘리먼트마다 한 작업을 실행해야 한다.
그러니 배열이 커질수록 시간도 늘어나는 $O(N)$ 이다.

배열 문제

  1. 배열 안에 데이터를 삽입하는 빅오는 무엇인가?
    ① $O(1)$
    ② $O(N)$
    ③ $O(N^2)$

    1번 정답

    답 : $O(1)$


  2. 배열 안에 데이터를 이동하는 빅오는 무엇인가?
    ① $O(1)$
    ② $O(N)$
    ③ $O(N/2)$

    2번 정답

    답 : $O(N)$


  3. forEach 함수를 위한 빅오는 무엇인가?
    ① $O(1)$
    ② $O(N/2)$
    ③ $O(N)$

    3번 정답

    답 : $O(N)$


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

댓글남기기

Recent posts