[알고리즘] 선형검색(Linear Search)와 이진 검색(Binary Search)
[알고리즘] 선형검색(Linear Search)와 이진 검색(Binary Search)
선형 검색(Linear Search)
다른이름으로 순차 검색(Sequential Search)이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다.선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다.
데이터를 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있습니다.
예를 들어 위와 같은 데이터의 집합이 있을 경우 4를 찾으려면 10번의 비교를 거쳐야 합니다.
100만개의 데이터가 있고 찾고자 하는 데이터가 100만번째에 있다면 100만번의 비교를 해야 한다는 뜻 입니다.
이와 같은 상황을 Worst Case라고 합니다.
관련된 용어로 평균적인 상황을 Average Case 좋은 상황을 Best Case라고 합니다.
이진 검색(Binary Search)
이진검색은 다른말로 이분검색이라고도 합니다. 반으로 나누어서 연산하기 때문이죠.선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘이지만 이진검색은 중간값부터 탐색을 합니다.
선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다.
이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있습니다. 그러나 이진검색을 하기 위해서 데이터의 집합이 반드시 정렬(Sort)되어야 한다는 단점이 있습니다. 이렇게 이야기하면 얼마나 빠른지 감이 잘 안올텐데, 예를 들어 70억명의 사람중 한 사람을 찾으려고 한다면, 선형검색은 Worst Case의 경우 70억번, 대략적으로 생각해도 35억번은 비교연산을 해야 하는데, 이진 검색은 최대 33번의 비교만으로도 원하는 데이터를 찾을 수 있습니다.
출처
댓글
댓글 쓰기