자바스크립트에서 사용되는 주요 배열 메서드의 시간복잡도에 대해서 알아보자?

[배경] 자료구조에 대해 공부하다보니

자료구조에 대해 공부하다보니 갑자기 궁금해진 것이 하나 있다. 이 때 까지 당연하게 사용하던 배열 메서드들의 시간복잡도는 어떻게 될까? 내부적인 구현은 숨겨져 있으니 일일이 계산할 수는 없더라도 눈에 보이는 동작만 봤을 때 해당 메서드들이 어떤 시간복잡도를 가지는지 알아보면 재밌을 것 같아서 해당 포스트를 작성해본다.

 

[기초 개념] 시간복잡도에 대한 개념

시간복잡도는 알고리즘이 문제를 푸는데 걸리는 시간을 의미한다. 여기서 시간이란 실제 시간을 의미하기 보다는 연산의 크기를 측정한 값이라고 이해하면 된다. 예를 들어 아주 전통적인 for 문을 사용하여 배열을 순회한다고 가정할 때, 이 때 배열의 길이인 n 이 증가할 때 마다 순회 하는데 필요한 연산의 횟수도 증가하게 된다. 그리고 이렇게 선형적으로 증가하는 경우를 Big5 표기법이라고 부르는 O(n) 으로 표기하는데 이를 선형 시간복잡도 라고 부른다.

 

Array.prototype.push() 과 .pop() 의 시간복잡도

push( ) : 배열의 뒤로 요소를 추가

우선 제일 많이 쓰는 push() 메소드의 시간복잡도는 뭘까? 이를 알아보기 위해 간단한 push 메소드를 이용한 예시를 만들어보자

const arr = [1,2,3,4,5];
arr.push(6);

console.log(arr) // [1,2,3,4,5,6]

 

이 예시에서 push 메소드는 인자로 전달받은 값(value) 을 배열의 뒤에 추가하는 역할을 수행 하므로, 시간복잡도는 O(1) 으로 상수시간복잡도가 된다. 

 

pop( ) : 배열의 뒤에서 부터 요소를 제거

그 다음에는 pop() 메소드를 살펴보자, 앞서 예시의 결과에서 pop() 메소드를 호출하면 배열의 제일 뒤에 있는 요소를 제거하게 된다.

const arr = [1,2,3,4,5];
arr.push(6);

console.log(arr) // [1,2,3,4,5,6]

arr.pop()

console.log(arr) // [1,2,3,4,5]

 

이 때, 배열의 뒤에서 요소를 제거하는 것도 연속된 메모리 공간에서 요소의 배치를 바꾸지 않기 때문에 push() 메소드와 동일하게 시간복잡도는 O(1) 으로 상수시간이 된다.

 

Array.prototype.unshift( ) 과 shifit( ) 의 시간복잡도

unshift(value) : 요소를 앞에서 부터 추가

그러면 배열의 요소를 앞으로 추가시키는 unshift() 메소드의 경우는? 일단 간단한 예시를 만들어보자

const arr = [1,2,3,4,5];
arr.unshift(6);

console.log(arr) // [6,1,2,3,4,5]

 

위 예시처럼 요소를 앞으로 추가시키는 경우에는 연속된 메모리 공간에 이미 차지하고 있는 1,2,3,4,5를 한 칸 씩 뒤로 이동시켜야 한다. 즉, 그 만큼 연산에 필요한 시간이 증가하게 되므로 시간복잡도는 선형 시간복잡도를 나타내는 O(n) 이 된다.

 

shift( ) : 요소를 앞에서 부터 제거

이 정도면 짐작이 되겠지만, shift() 메소드의 경우에도 배열의 요소를 앞에서 부터 제거하게 되면, 해당 공간의 공백을 채우기 위해 뒤에 있던 요소들이 앞으로 한 칸 씩 이동하게 되고, 이로 인해 CPU 연산에 드는 시간이 선형적으로 증가하므로 시간복잡도는 O(n) 이 된다. 

const arr = [1,2,3,4,5];
arr.unshift(6);

console.log(arr) // [6,1,2,3,4,5]

arr.shift();

console.log(arr) // [1,2,3,4,5]

 

Array.prototype.splice( )

자주 사용하는 메소드 중에서 splice() 메소드도 있다. 해당 메소드에 대해 곰곰이 생각해봤는데, 이 친구의 경우에는 원본 배열을 직접적으로 파괴하는 친구이기 때문에 어떻게 사용하느냐에 따라서 시간복잡도가 상수시간이 될 수도 있고, 선형 시간이 될 수 있다는 생각이 들었다.

 

보통 splice 를 사용하는 경우는 원본 배열에서 특정 요소를 제거하는 것이 주용도 이므로 시간복잡도는 메모리공간 상의 요소 배치를 바꾸는 만큼 O(n) 시간복잡도를 가진다.

 

Array.prototype.indexOf( )

해당 메소드는 넘겨받은 값(value)이 접근한 배열에서 어디에 위치하는지 찾고, 해당 위치의 인덱스를 반환하는 친구인데, 이 친구의 경우에는 접근한 배열 전체를 순회하여 타겟이 되는 값(value) 과 일치하는 요소를 찾기 때문에, 선형시간복잡도인 O(n) 을 가진다.

 

Array.prototype.sort( )

이 친구에 대해서는 갈피가 잡히지 않아서 찾아보니 내부적으로 퀵 정렬 알고리즘을 사용하고 있다고 한다. 퀵 정렬 알고리즘의 시간 복잡도는 O(n log n) 으로 나타난다고 한다.

 

n log n 는 n(연산 횟수)이 증가할 때 마다 실행 시간은 log n 만큼만 증가한다는 의미로 보통 분할과 정복 패턴을 사용하는 알고리즘에서 평균적으로 나타난다고 한다. 이에 대한 공부가 미흡하므로 알고리즘을 차츰 공부해 가면서 알아가야 겠다.

 

[나가는 길] 멀고도 멀다

자료구조에 대한 공부를 진지하게 시작한지 얼마 되지 않아서 그런가 자료구조와 알고리즘에 대해 알아가는 시간이 흥미롭게 다가오는 것 같다. 왜 이러한 즐거움을 늦게 알았나 싶다. 

 

현재 까지는 지식과 이해에 구멍이 많아서 명확하게 설명할 수준은 아닌 것 같다. 그럼에도 시간복잡도와 공간복잡도에 대한 개념을 어느 정도 알고 나니 이 때 까지 그냥 편리해서 사용하기만 했던 메소드나 로직에 대해서 다른 시각으로 바라보는 계기가 되고 있다.

 

프론트엔드 개발에서 알고리즘과 자료구조에 대한 공부가 그렇게 필요하지 않다는 말을 개발 공부를 처음 시작했을 때 부터 자주 접했는데, 그건 아닌 것 같다. 우리가 벌써 당연하게 사용하고 있는 모든 것들이 자료구조이고 알고리즘인데 내가 사용하는 것이 연산 시간이 오래 걸리는 로직일지, 메모리 공간을 불필요하게 많이 사용하는 로직이 아닐지, CPU가 할 일을 계속해서 늘려주고 있는 것이 아닌지 등등에 대해서 알아야 보다 효율적이고 좋은 코드를 작성해 나갈 수 있다는 생각이 든다.

 

참고자료

mdn 공식문서 자바스크립트 메서드 부분 전반

코딩팩토리 기술 블로그 https://coding-factory.tistory.com/615

네이버 공식 기술 블로그 https://d2.naver.com/helloworld/0315536