선형 탐색

선형 탐색

개요

선형탐색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색합니다.

효율성과 비효율성

선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다.
선형탐색은 자료가 정렬되어 있지 않거나 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다. 이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다.
정렬은 시간이 오래 걸리고 공간을 더 차지합니다. 하지만 이 추가적인 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있습니다.