알고리즘 기초 - 선형 및 이진 탐색

선형 알고리즘(Linear Algorithm)

선형 알고리즘의 실행 시간은 요소 개수 증가에 정비례하여 증가하므로 시간 복잡도는 O(n)이다.

선형 알고리즘은 데이터쌍(인덱스와 이에 매칭되는 값)을 이용해 선형적으로 요소를 탐색하는 방법이다.

선형 탐색은 결과를 얻기 위해 배열의 모든 요소를 살펴봐야하므로 느리다. 선형 탐색은 모든 유형의 데이터에 적용할 수 있지만 비효율적이다.

 

이진 탐색 알고리즘

선형 탐색을 보완하는 로그형 탐색 기술이다. 이진 탐색의 시간 복잡도는 O(logn)이다. 선형 탐색에서 시간 복잡도가 O(1)인 경우를 제외하면 선형 탐색보다 훨씬 효율적이다.

 

1. 배열의 중간 요소를 찾는다. 

2.찾고 있는 숫자보다 작은 숫자를 삭제한다. (중간요소보다 앞에 있는 요소들을 삭제)

반복.

 

이진 탐색은 한번 검색할 때마다 배열을 반으로 나눠 검색 대상에서 제외한다. 선형 탐색보다 더 길고 복잡해 보일 수 있지만 배열의 크기가 아주 크다면 이진 탐색은 선형 탐색보다 처리 속도가 빨라 간단한 알고리즘이 된다.

이진 탐색같은 로그형 알고리즘의 시간 복잡도는 n이 기하급수적으로 증가하더라도 시간은 같은 비율로 증가하지 않는다.

요소가 많을수록 요소 하나당 탐색에 걸리는 시간이 짧아진다. 간단한 탐색을 할 때보다 복잡한 탐색을 할 때 단위 속도가 큰 폭으로 향상된다.

 

단, 이진 탐색은 배열이 정렬된 상태에서만 올바르게 동작한다.