[JAVASCRIPT][CS] 자바스크립트 배열의 시간 복잡도

제주코딩베이스캠프 Code Festival: JavaScript 100제

문제31 '자바스크립트 자료형의 복잡도' 와 관련이 있습니다.

---

시간 복잡도

알고리즘을 처리하는 데 얼마의 시간이 걸리는지 측정하는 척도를 의미한다.

만일 개발자가 시간 복잡도가 좋지 않은 코드를 작성하면, 프로젝트에도 악영향을 줄 수 있다

 

Big-O (빅오 표기법)

알고리즘의 성능을 수학적으로 표현해주는 표기법이다.

알고리즘의 시간 복잡도, 공간 복잡도를 표현해 해당 알고리즘이 얼마나 효율적인지를 나타낸다.

데이터나 사용자 증가율에 따른 알고리즘 성능을 예측하기 위해 사용한다.

 

Big-O 의 예

O(1)

Constant Time. 상수 시간

입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 표현한다.

n의 크기와 상관 없이 연산을 한 번에 시도한다.

function exampleConstant(arr) {
	console.log(arr[0]);
}

 

O(n)

Linear Time. 선형 시간

입력 데이터의 크기에 비례해서 처리시간이 늘어나는 알고리즘을 표현한다.

최대 n번의 연산을 수행하며, for문이 일반적인 예시다.

function exampleLinear(n) {
	for (let i = 0; i < n; i++) {
		console.log(i);
	}
}

 

O(n²)

Quadratic Time. 2차 시간

입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘을 표현한다.

n의 크기가 커질수록 처리시간의 부담이 늘어나며, for문 안의 for문이 일반적인 예시다.

function exampleQuadratic(n) {
	for (let i = 0; i < n; i++) {
		console.log(i); 
		for (let j = i; j < n; j++) {
			console.log(j);
		}
	}
}

 

O(logN)

Log time. 로그 시간

연산 한 번 수행할 때 마다 검색해야 하는 데이터 양이 절반씩 떨어지는 알고리즘을 표현한다.

이진 탐색 등의 알고리즘을 표현할 때 사용한다.

function exampleLogarithmic(n) {
	for (let i = 2; i <= n; i*2) {
		console.log(i);
	}
}

 

Big-O 그래프 : 시간 복잡도 비교

O(1) < O(log n) < O(n) < O(N log n) < O(n²) < O(2ⁿ)

 

Big-O 의 값이 크다
= 수행 시간이 길다
= 시간 복잡도가 복잡하다

 

 

 

---

배열에서의 시간 복잡도

배열에서 자주 사용하는 함수/메서드의 시간 복잡도를 아래와 같이 정리할 수 있다.

push	배열의 맨 끝에 값을 삽입	O(1) : 맨 끝의 값 인덱스만 영향
pop	배열의 맨 끝의 값을 삭제	O(1) : 맨 끝의 값 인덱스만 영향
shift	배열의 맨 앞에 값을 삽입	O(N) : 다른 값들의 인덱스에 영향
unshift	배열의 맨 앞의 값을 삭제	O(N) : 다른 값들의 인덱스에 영향
concat	배열을 이어줌	O(N) : 다른 값들의 인덱스에 영향
slice	배열을 지정해놓은 영역부분으로 자름	O(N) : 다른 값들의 인덱스에 영향
splice	배열에 지정해놓은 인덱스에 값들을 추가하거나, 자름	O(N) : 다른 값들의 인덱스에 영향
sort	배열을 정렬한다.	O(NlogN)
forEach map filter reduce	배열에 사용하는 주 메서드들	O(N) : 배열의 길이만큼 순회

• 배열의 모든 요소를 방문해야 하는 경우 : O(N)
• push/pop 을 이용하는 것이 shift/unshift 를 이용하는 것 보다 시간적으로 유리하다.

 

 

---

참고

[Javascript] 시간 복잡도 정리 및 예제

[JS] 자바스크립트 배열 시간 복잡도

[자료구조] 시간복잡도 with JavaScript