탐색 알고리즘의 종류

탐색 알고리즘의 종류

1. 선형 탐색
2. 이진 탐색
3. 해쉬

선형 탐색 알고리즘 Linear Search

Definition

전체 리스트를 하나씩 확인해 가며 찾는 방법

Time complexity

O(n)

특징

• 모든 데이터 타입에 사용 가능
• n만큼의 용량 필요

이진 탐색 알고리즘 Binary Search

Definition

전체 리스트에서 가운데를 비교하고 그 수가 원하는 수보다 작을 경우, 왼쪽의 작은 숫자 리스트는 버리고 나머지 오른쪽에서 다시 찾는 방법. 절반씩 줄여가며 찾는 방법

Time complexity

O(log n)

특징

• 전제 조건: 정렬이 되어 있어야 함
• 전제 조건: 입력할때마다 재 정렬 필요.
• 입력할때마다 재정렬이 필요하므로, 출력보다 입력이 많을 경우 프로그램이 느려질수 있음
• divide-and-conquer 기법 중 하나

해쉬 hashing

Definition

해쉬코드를 어드레스 삼아서 찾는 방법
Hash map 혹은 Hash table을 사용

Time complexity

O(1)

특징

• 모든 데이터에 사용 가능
• n보다 큰 용량 필요
• 해쉬 충돌이 일어날 경우, 느려질수가 있다

결론

배열을 탐색 할 일이 많다 -> 이진 탐색
배열을 추가 할 일이 많다 -> 선형 탐색
용량이 커도 좋다. 무조건 빨라야 한다 -> 해쉬