Array.prototype.includes와 Map.prototype.has는 시간복잡도에서 큰 차이가 있습니다.
1. includes: 선형 탐색 ((O(n)))
- 배열(Array)의
includes메서드는 배열의 각 요소를 처음부터 끝까지 순회하며, 지정된 값이 있는지 확인합니다. - 최악의 경우, 배열의 길이 (n)만큼의 요소를 모두 확인해야 하므로 시간복잡도는 (O(n))입니다.
예시:
const arr = [1, 2, 3, 4, 5];
console.log(arr.includes(3)); // true- 내부적으로 배열을 순회하면서
3이 있는지 확인합니다. - (O(n)) 탐색으로 동작합니다.
2. has: 상수 시간 ((O(1)))
- 해시맵(Map)이나 셋(Set)의
has메서드는 키가 존재하는지 확인할 때, 해싱 알고리즘을 사용합니다. - JavaScript의
Map객체는 내부적으로 해시 테이블을 사용하여 키를 저장하므로, 특정 키가 있는지 확인하는 연산은 평균적으로 상수 시간((O(1)))에 실행됩니다.
예시:
const map = new Map();
map.set(1, 'one');
map.set(2, 'two');
console.log(map.has(2)); // truehas(2)는 (O(1))에 동작하며, 배열 탐색과는 달리 상수 시간으로 키를 찾습니다.
주요 차이점
| 메서드 | 자료구조 | 시간복잡도 | 설명 |
|---|---|---|---|
includes | 배열(Array) | (O(n)) | 값이 있는지 찾기 위해 배열 전체를 순회합니다. |
has | 해시맵(Map), 셋(Set) | (O(1)) | 키를 바로 조회하며, 해싱을 통해 상수 시간에 동작합니다. |
실전 비교
배열에서 includes를 사용할 경우:
const arr = [1, 2, 3, 4, 5];
console.log(arr.includes(3)); // true- 시간복잡도: 최악의 경우, 배열의 모든 요소를 순회 ((O(n))).
해시맵에서 has를 사용할 경우:
const map = new Map();
map.set(1, 'one');
map.set(2, 'two');
console.log(map.has(2)); // true- 시간복잡도: 키를 해시 테이블에서 직접 찾으므로 상수 시간 ((O(1))).
결론
- 배열의
includes는 (O(n))로 비효율적일 수 있지만, 간단한 경우에는 사용하기 편리합니다. - 많은 데이터를 처리하거나 중복 확인 등의 작업을 빠르게 수행해야 한다면, 해시맵의
has를 사용하는 것이 더 효율적입니다.
