서론
이제 검색 알고리즘 section에 들어왔다. 흔히 쓰는 검색 알고리즘은 구글링을 하는 것 부터 회원가입에 이르기까지 아주 다양하게 쓰이고 있다. 오늘 이야기할 것은 그 많은 검색 알고리즘 중 선형검색 알고리즘이다.
본론
선형검색 알고리즘
- 선형의 데이터에서 사용되는 알고리즘
- 비정렬된 데이터에서 효과적으로 사용됨.
- 최고의 시간 복잡도는 O(1) 최악의 시간복잡도는 O(n)
선형검색 알고리즘이란?
우리가 간단하게 자주 쓰는 알고리즘 중 하나이다. 정렬되지 않은 데이터에서 원하는 데이터를 찾을 때 주로 사용되는데 순차적으로 왼쪽에서 오른쪽이든 오른쪽에서 왼쪽이든 한방향으로 데이터를 하나하나 비교하면서 대조하는 알고리즘을 이야기한다. 해당 알고리즘은 시간 복잡도가 O(n)이기 때문에 비효울적으로 보일 수도 있지만, 그래도 나쁜 알고리즘은 아니다. 왜냐면 우리가 주로 쓰는 메서드에서도 많이 사용하는 알고리즘이기 때문이다.
그 예를 들자면 우리가 흔히 쓰는 indexOf같은 메서드에서도 같은 알고리즘을 사용하고 있다. indexOf를 실행하면 내부에서 어떤식으로 진행되는지 코드로 한 번 구현해 보겠다. indexOf는 파라미터로 받은 데이터가 존재하면 그 해당 인덱스를 반환하고, 존재하지 않으면 -1을 반환한다.
function indexOf(arr, data){
for(let i = 0; i<arr.length; i++){
if(arr[i] === data){
return i;
}
}
return -1;
}짠 이렇게 간단하게 구현이 가능하다. indexOf에서는 이런 식으로 동작하고 있던 것이다.
\선형검색 알고리즘은 가장 기본적이고 가장 우리가 많이 쓰는 알고리즘 중 하나이다.
참고
웹개발