[JS100] 31번 문제 (시간 복잡도)

Q.31

다음 배열 내장함수의 시간 복잡도가 O(1)이 아닌 것을 모두 고르시오.

1) arr[i]
2) arr.push(5)
3) arr.slice()
4) arr.pop()
5) arr.includes(5)

Answer

3)  arr.slice()
5)  arr.includes(5)

 

 

참고 개념 

시간 복잡도

O(1)

상수 시간 복잡도이다. 

function twoUp(num) {
  return num+num;
}

num에 어떤 수가 들어와도 + 한번의 연산을 시도한다. 연산이 여러 번 시행되도 시간 복잡도는 O(1)로 동일하다.

무한대를 기준으로 봤을 때 그래프 형식은 비슷하기 때문에 동일하게 표기하는 걸 규칙으로 한다.

function upupup(num) {
  return num+num+num+num+num+num+num+num+num+num+num+num+num+num+num;
}

O(logN)

logN만큼의 시간 복잡도이다. 간단한 예로 2개의 자식노드를 가지는 이진트리를 이용해 8개의 노드중 원하는 값의 노드를 찾는다고 생각해보자. 그럼 2개의 자식노드로 인해 8 => 4 => 2 => 1 순서로 찾을 수 있을 것이다. 

 

O(N)

n만큼의 시간 복잡도이다. 간단하게 for문을 생각하면 된다.

function count(num) {
  let count = 0;
  for(let i = 1; i <= num; i++){
    if(i%2 === 1) {
      count += 1;
    }
  }
  return count;
}

O(1)과 다르게 num이 10,000이라면 10,000번 순회하고, 1,000,000이라면 1,000,000번 순회한다. 즉 num만큼 순회하므로 O(n)으로 표기할 수 있다. 마찬가지로 4개의 for문이 있어도 O(4n)이 아니라 그냥 O(n)으로 표기한다.

 

O(NlogN)

N*logN만큼의 시간 복잡도

 

O(N^2)

n^2만큼의 시간 복잡도 대표적으로 2중 for문이 있다.

function matrix(num) {
  const mat = [];
  for(let i = 0; i < num; i++){
    const row = [];
    for(let j = 0; j < num; j++) {
      row.push([i,j]);
    }
    mat.push(row);
  }
}

위 코드에서 num이 1000이라 생각해보자, 얼핏 봐도 1,000,000번 실행된다는 걸 알 수 있다. 다른 복잡도에 비해 많은 시간이 걸리므로 수학적 공식 등을 활용해 효율적으로 사용하는 게 좋다.

---

배열에서의 시간 복잡도

우선 배열에서 우리가 자주 사용하는 함수 및 메서드들을 살펴보자.

push	배열의 맨 끝에 값을 삽입한다.
pop	배열의 맨 끝의 값을 삭제한다.
shift	배열의 맨 앞에 값을 삽입한다.
unshift	배열의 맨 앞의 값을 삭제한다.
concat	배열을 이어준다.
slice	배열을 지정해놓은 영역부분으로 자른다.
splice	배열에 지정해놓은 인덱스에 값들을 추가하거나, 자른다.
sort	배열을 정렬한다.
forEach, map, filter, reduce	배열에 사용하는 주 메서드 들

 

push, pop : O(1) 

배열은 우리가 알다시피 인덱스를 가진다. 첫 시작은 0, 끝의 인덱스 값은 배열의 길이 -1이다. push, pop은 배열의 맨 끝에 값을 추가 및 삭제 하므로 인덱스 하나만 지정해주거나 삭제하면 된다. 시간 복잡도는 O(1) 이다.

 

shift, unshift : O(N)

앞에다 값을 삽입하거나 삭제하는 shift, unshift는 배열의 인덱스에 많은 영향을 끼친다. 예로 앞의 값을 추가한다고 생각해보자.

 

[ 1, 2, 3, 4, 5 ]

   0   1   2   3   4                 

 

해당 배열 앞에 0 값을 추가하면 인덱스는 앞으로 한 칸씩 밀리고 뒤에 하나가 추가될 것이다.

 

[ 0, 1, 2, 3, 4, 5 ]

   0   1   2   3   4   5

 

이렇게 값을 앞에 추가함으로 인해 전체 인덱스가 바뀌므로 시간 복잡도는 O(N) 이다.

 

concat, slice, splice : O(N)

배열을 이어주고, 자르고, 값을 추가하면 인덱스를 조정해줘야하므로 O(N)으로 생각

 

forEach, map, filter, reduce :  O(N)

배열의 메서드도 결국 배열의 길이만큼 배열을 순회해야하므로 O(N)으로 생각

sort : O(NlogN)

인자값으로 넘어온 함수에 따라 값을 정렬한다. 기본적으로 내장 sort를 사용할 때 크롬에서 퀵 정렬을 사용한다.

평균적으로 NlogN의 시간 복잡도를 가진다.

const arr = [1,26,76,85,3];

arr.sort((a, b) => a - b);

console.log(arr) // [1, 3, 26, 76, 85]