자료형의 복잡도 O(1) O(n)

JavaScript 자료형의 복잡도

---

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

다음 5가지 항목중 내장함수의 시간 복잡도가 O(1)이 아닌 것을 찾아보자.

💡Big O가 무엇인지 알아보자.

실행할 때 필요한 단계 수를 의미한다. 단계 수가 왜 중요할까? 날이 갈수록 컴퓨터 성능이 좋아져서 예전과는 비교할 수 없지만 필요한 단계 수가 1이라면 아주 빠르게 되는 것을 알 수 있다. 하지만 필요한 단계 수가 100일 경우에 컴퓨터의 성능을 제외한다면 단계 수가 1인 것보다 느리게 처리된다는 것을 알 수 있다.

Big O는 실행에 필요한 단계 수를 나타내는 것을 의미한다.

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

O(1)은 "Big O 1"이라고 읽고, O(n)은 "Big O n"이라고 읽는다. "Big O 1"에서 1은 단계 수를 의미한다. 한 단계가 걸린다는 뜻이다. n은 무엇일까? 자료구조의 길이만큼 걸린다는 뜻이다.

💡정리

배열에서 읽기는 O(1)이다. 컴퓨터는 index를 통해서 바로 값을 읽을 수 있기 때문이다. 배열의 마지막에 값을 삽입하거나, 배열의 마지막에 값을 넣는 것 또한 바로 실행되기 때문에 O(1)이다. 정답은 3번, 5번이다. slice() 메서드의 경우 배열을 복사하고, 빈 값을 만들고 원래 값을 돌면서 push한다. includes() 메서드 또한 배열의 첫 index부터 돌면서 값이 존재하는지 확인하기 때문에 O(n)이다.