배열 메서드와 시간 복잡도의 관계
배열 챕터를 시작하면서 해시 테이블, 시간 복잡도 등의 CS 용어, 지식들을 마주치게 됐다. 시간 복잡도, 특히 Big-O라는 용어를 종종 접하긴 했었지만 나랑은 상관 없으니까ㅋ 하며 넘겼었다.
그러나 어쩌다 reduce 메서드와 ES6의 ...Rest 파라미터에 대한 블로그를 읽게 됐는데 읽다보니 아 메서드를 그냥 외워서 아무데나 쓸게 아니라 그 메서드가 어떻게 동작하는지를 이해하는것도 중요하겠다 라는것을 느꼈다.
Array.prototype.indexOf
indexOf 메서드는 원본 배열에서 인수로 전달된 요소를 검색해 그 요소의 인덱스를 반환한다.
- 원본 배열에 인수로 전달한 요소가 중복된다면 첫번째로 검색된 요소의 인덱스 반환.
- 원본 배열에 인수로 전달한 요소가 존재하지 않으면 -1을 반환.
이러한 특징으로 indexOf메서드는 배열에 특정 요소가 존재 하는지 / 안하는지 확인하기에 유용해 보인다.
(🤔그렇다면 includes 메서드와 비교했을 때 내부 동작에는 어떤 차이가 있을까?)
const arr = ['키','열쇠','시계','지갑']
const search = '핸드폰'
if(arr.indexOf(search) === -1){
console.log(`${search}이(가) 없습니다.`)
}else if(arr.indexOf(search) !== -1){
console.log('통과')
}
// '핸드폰이(가) 없습니다.'indexOf의 시간 복잡도는 뭐지?
원본 배열에 인수로 전달한 요소가 중복된다면 첫번째로 검색된 요소의 인덱스 리턴한다. 예를들어 배열의 두번째에 찾고자 하는 요소가 있다면 굉장히 빨리 검색이 끝날것이다. 하지만 만약 최악의 상황으로 2^38개의 요소를 가진 배열에 검색중인 값이 없다면 배열의 요소를 n개 다 순회해야 한다. 따라서 indexOf의 시간복잡도는 O(n)이 되겠다.
for문으로 구현해 비교해보기?
for문으로 indexOf와 같은 동작을 재연해보자.
const arr = Array.from({length:10000000})
arr[9999999] = 1
const searchItem = 1
// for문으로 검색
console.time('for performance test')
const searchIndexFunc = (function(){
for(let i = 0; i < arr.length; i++){
if(arr[i] === searchItem){
return i
}
}
return -1
}())
console.timeEnd('for performance test')
console.log(searchIndexFunc)
// for performance test: 27.033203125 ms
// 9999999😧😧😧 indexOf를 사용했더니 훨신 빠른걸 볼수있다. 왜지..?
console.time('indexOf performance test')
const searchIndexMethod = arr.indexOf(searchItem)
console.timeEnd('indexOf performance test')
console.log(searchIndexMethod)
// indexOf performance test: 8.712158203125 ms
// 9999999검색해보니 퍼포먼스 시간은 잴때 호출에 의한 차이일 수도 있고 상황에 따라 바뀔수 있다고 한다. 이 부분은 좀 더 공부해봐야겠다.
👀 indexOf 모르고 풀었던 알고리즘 연습 문제를 다시 봐보았다.
문제 설명
String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.
제한 사항
seoul은 길이 1 이상, 1000 이하인 배열입니다.
seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다.
"Kim"은 반드시 seoul 안에 포함되어 있습니다.
제출했었던 답:
function solution(seoul) {
let idx = 0;
const search = 'Kim'
for(let i = 0;i < seoul.length; i++){
if(search === seoul[i]){
idx = i;
break;
}
}
var answer = `김서방은 ${idx}에 있다`;
return answer;
}저걸 다시 작성해본다면 요렇게 작성할듯
- 지역 변수 idx, answer들을 없앴다.
- break 대신 return으로 for문 종료와함께 함수를 같이 종료
function solution(seoul) {
const search = 'Kim'
for(let i = 0;i < seoul.length; i++){
if(search === seoul[i]){
return `김서방은 ${i}에 있다`
}
}
}
solution(["Jane", "Kim"])다시 오늘 배운 indexOf로 작성해본다면?
function solution(seoul) {
const search = 'Kim'
if(seoul.indexOf(search) === -1){
return "김서방이 없습니다."
}
return `김서방은 ${seoul.indexOf(search)}에 있다`
}
solution(["Jane", "Kim"])참조 링크
1. Time complexity Big 0 for Javascript Array methods and examples.
2. reduce 와 ... 은 같이 쓰지마!
3.자바스크립트의 자료구조 1 : 배열(Array)
