[알고리즘/Python] 선형 탐색

1. 개요

💡 선형 탐색(Linear Search) 이란?

• 배열이나 리스트의 처음부터 끝까지 하나씩 값을 비교하면서 찾는 값을 찾을 때 까지 탐색하는 방법입니다.
• 선형 탐색의 경우 '정렬 되지 않은 상태' 배열/리스테엇 값을 찾기 위한 탐색에 사용합니다.

2. 선형 탐색 동작 과정

1. 배열/리스트를 순회합니다.

2. 배열/리스트를 순회하면서 하나씩 값을 비교합니다.

3. 원하는 값을 찾는 경우 순회를 멈추고 값을 반환합니다.

3. 선형 탐색 vs 이진 탐색

분류	선형탐색	이진탐색
정렬여부	정렬되지 않은 배열/리스트	정렬된 배열/리스트
탐색속도	느림	빠름
탐색범위	처음부터 끝까지	중간값을 기준으로 좌/우측 반 중 하나
구현방식	for/while 루프 사용	재귀 함수 사용
시간 복잡도	O(n)	O(logn)

4. 선형 탐색의 사용처

💡 데이터의 크기가 작거나 정렬되어 있지 않은 경우에 주로 사용이 됩니다. 
💡 예를 들어, 10개 이하의 원소로 이루어진 리스트에서 값을 찾을 때는 선형 탐색이 효율적입니다.
💡 하지만 데이터의 크기가 커지면 검색 속도가 급격히 느려지므로, 큰 데이터셋에서는 다른 탐색 알고리즘을 사용하는 것이 좋습니다.

5. 선형 탐색의 시간 복잡도

💡 선형 탐색의 경우 시간 복잡도의 ‘빅오 표기법’을 이용하여 확인하였을때 선형 시간인 O(n)으로써 이진 탐색보다는 느리지만 상대적으로 빠른 속도를 가지고 있습니다.

표기법	이름	시간복잡도	설명	예시
O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가진다.	배열에서 원소 하나 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가한다	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행시간	선형 탐색 알고리즘
O(nlogn)	로그선형	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가한다.	퀵정렬, 병합 정렬, 힙 정렬 알고리즘
O(N^2)	이차	이차 시간(제곱 시간)	입력 크기의 제곱에 비례하는 실행 시간을 가진다.	선택정렬, 버블 정렬, 퀵 정렬
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가지낟.	부분 집합
O(n!)	계숭	팩토리얼 시간	입력크기의 팩토리얼에 비례하는 실행 시간을 가진다.	외판원 문제