JavaScript 배열 메소드의 시간복잡도

 

시작하면서

자바스크립트 배열 메서드에 관한 시간 복잡도를 공부합니다.

 

 

배열 메소드의 시간 복잡도

시간 복잡도란?

시간 복잡도란 간단하게 말해서 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말합니다.

시간 복잡도 표시는 빅오 표기법을 사용하였습니다. 알고리즘의 효율성을 표기해주는 표기법입니다.

 

배열 메서드 시간 복잡도

배열에서 많이 사용하는 메서드들의 시간 복잡도를 알아보도록 하겠습니다. 

 

1. push() - O(1)

배열 끝에 새로운 요소를 추가해주는 메서드입니다.

일정한 O(1)의 복잡도를 갖습니다. 입력값이 증가하더라도 시간은 변하지 않습니다.

const names = ['Luis','John','Jose'];
names.push("Aaron");
console.log(names); // (4) ["Luis", "John", "Jose", "Aaron"]

 

2. pop() - O(1)

배열 끝 요소를 삭제해주는 메서드입니다.

일정한 O(1)의 복잡도를 갖습니다. 입력값이 증가하더라도 시간은 변하지 않습니다.

const names = ['Luis','John','Jose','Aaron'];
console.log(names.pop()); //Aaron
console.log(names); // (3) ["Luis", "John", "Jose"]

 

3. shift() - O(n)

배열의 첫번째 요소를 삭제해주는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const names = ['Luis','John','Jose','Aaron'];
console.log(names.shift()); // Luis
console.log(names); // (3) ["John", "Jose", "Aaron"]

 

4. unshift() - O(n)

배열의 시작 부분에 하나 이상의 요소를 추가하는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const names = ['Luis','John','Jose'];
console.log(names.unshift("Aaron")); // 4
console.log(names); // (4) ["Aaron", "Luis", "John", "Jose"]

 

5. splice() - O(n)

특정 요소를 제거하거나 추가 또는 교체하는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const months = ["Jan", "March", "April", "June"];
months.splice(1, 0, "Feb");
// inserts at index 1
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "June"]

months.splice(4, 1, "May");
// replaces 1 element at index 4
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "May"]

 

6. sort() - O(n log(n))

배열요소를 정렬해주는 메서드 입니다.

데이터가 많아지수록 처리시간이 로그(log) 배만큼 더 늘어나는 O(n log(n))의 복잡도를 갖습니다. 데이터가 10배라면, 처리시간은 약 20배를 갖는 복잡도입니다. 

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]

 

7. concat() - O(n)

2개 이상의 배열을 합쳐주는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const names1 = ["Luis","Jose"];
const names2 = ["John","Aaron"];
const newArray = names1.concat(names2,["Michelle"]);
console.log(newArray); // (5) ["Luis", "Jose", "John", "Aaron", "Michelle"]

 

8. slice() - O(n)

어떤 배열의 시작부터 끝까지(끝은 포함하지 않습니다) 잘라서 복사본을 새로운 배열 객체로 반환하는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

console.log(animals.slice(1, 5));
// expected output: Array ["bison", "camel", "duck", "elephant"]

console.log(animals.slice(-2));
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// expected output: Array ["camel", "duck"]

console.log(animals.slice());
// expected output: Array ["ant", "bison", "camel", "duck", "elephant"]

 

9. indexOf() - O(n)

배열에 존재하는 요소를 찾아서 해당 인덱스를 반환해주는 메서드입니다. 여러개일 경우 가장 첫번째만, 없을 경우엔 -1을 반환합니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const names = ['Luis','Jose','John','Aaron'];
console.log(names.indexOf("John")); // 2
console.log(names.indexOf("Michelle")); // -1

 

10. forEach() - O(n)

배열의 각 요소에 대해 함수를 시행하는 메서드 입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const array1 = ['a', 'b', 'c'];

array1.forEach(element => console.log(element));

// expected output: "a"
// expected output: "b"
// expected output: "c"

 

11. map() - O(n)

배열의 각 요소에 대해 함수를 시행하는 메서드 입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const array1 = [1, 4, 9, 16];

// pass a function to map
const map1 = array1.map(x => x * 2);

console.log(map1);
// expected output: Array [2, 8, 18, 32]

 

12. filter() - O(n)

주어진 필터 조건을 통과하는 모든 요소를 모아 새로운 배열로 반환하는 메서드 입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const words = ['spray', 'limit', 'elite', 'exuberant', 'destruction', 'present'];

const result = words.filter(word => word.length > 6);

console.log(result);
// expected output: Array ["exuberant", "destruction", "present"]

 

13. reduce() - O(n)

배열의 각 요소에 대해 주어진 리듀서 (reducer) 함수를 실행하고, 하나의 결과값을 반환하는 메서드입니다.

선형복잡도라고 부르는 O(n)의 복잡도를 갖습니다. 입력값의 증가도에 따라 시간도 동일한 비율로 증가합니다.

const array1 = [1, 2, 3, 4];

// 0 + 1 + 2 + 3 + 4
const initialValue = 0;
const sumWithInitial = array1.reduce(
  (accumulator, currentValue) => accumulator + currentValue,
  initialValue
);

console.log(sumWithInitial);
// expected output: 10

 

 

마무리하며

이렇게 각 JavaScript 배열 메서드의 시간 복잡도에 대해서 알아보았습니다.

차후에 배열 메서드를 이용한 기능을 만들 때 시간 복잡도를 생각하면서 구현하면 좋을 듯 합니다.

 

Reference

https://dev.to/lukocastillo/time-complexity-big-0-for-javascript-array-methods-and-examples-mlg

Time complexity Big 0 for Javascript Array methods and examples.