문제 31 : 자바스크립트 자료형의 복잡도

문제 31 : 자바스크립트 자료형의 복잡도

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

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

빅 오란 무엇일까?

무언가를 실행하는데 필요한 단계수를 나타내는게 빅오라고 할 수 있다.
단계수가 왜 중요할까?
컴퓨터가 성능이 아주 빨라져서 예전과는 비교할 수 없지만 필요한 단계수가 1이라면 아주 빠르게 진행될 것을 알 수 있다. 하지만 필요한 단계수가 100이라면 컴퓨터의 성능을 제외하면 단계수가 1인 것보다 느리게 진행된다는 것을 알 수 있다.
즉 빅오는 알고리즘에 필요한 단계 수를 나타내는 것이다.

O(1)과 O(n)의 의미

O(1)은 “빅 오 1”이라고 읽는다. O(n)은 “빅 오 엔”이라고 읽는다.
뜻을 설명하자면 1은 단계수를 나타낸다. 즉 한단계가 걸린다는 것이다. 그렇다면 n은 무엇을까? 바로 자료구조의 길이만큼 만큼 걸린다는 뜻이다.

const arr = [1, 2, 3, 4, 5];

위와 같이 arr같은 배열이 있다. 이 배열에 숫자 3이 들어 있는지 확인하는 방법은 무엇일까?
바로 순서대로 값을 하나씩 비교하는 것이다. 즉 맨처음 인덱스 0번을 보고 3인지 확인하고 아니면 인덱스 1을 본다. 이와 같이 실행하다가 만약 3이 없으면 없다고 반환한다. 지금은 중간에 있지만 마지막에 3이 있었다면 모든 값을 다 확인하게 된다.
이게 O(n)이라고 할 수 있다.

풀이 1

배열에서 읽기는 O(1)이라고 할 수 있다. 컴퓨터는 인덱스를 통해서 바로 값을 읽을 수 있기 때문이다. 그리고 배열의 마지막에 값을 삽입하거나, 배열의 마지막에 값을 넣는 것 또한 O(1)이다. 그래서 정답은 그 이외의 것인 3번과 5번이다.
중간에 넣거나 빼는 것은 왜 O(1)이 아닐까?
넣기 위해 값을 미뤄야하거나, 삭제하고 난 뒤에 중간에 값을 땡겨와야 하는 과정이 있기 때문이다.
slice의 경우 배열을 복사한다. 복사하기 위해서는 빈 값을 만들고 원래 값을 돌면서 push작업을 해준다. 또한 includes는 처음 값부터 하나하나씩 다 찾으면서 값이 들어있는 지 확인하기 때문에 O(n)이다.