검색 알고리즘 분석

검색 알고리즘 분석¶

검색은 어떤 집합과 목표 대상을 받아 그 대상이 해당 집합에 들어있는지를 판별하고 때론 대상의 인덱스를 반환해 주는 알고리즘이다.

가장 단순한 검색 알고리즘은 '선형검색'으로, 집합의 항목들을 순서대로 지나가다가 대상을 찾으면 멈춘다. 최악의 경우 집합을 끝까지 지나야 하는 경우도 있으므로 실행시간이 선형이다.

시퀀스에 사용하는 in 연산자는 선형검색을 사용한다. find나 count 같은 문자열 메소드도 마찬가지다.

만약 시퀀스에 들어있는 원소들이 순서대로 되어있다면, O(log n)인 이분검색을 사용할 수 있다. 이분검색은 여러분이 사전에서(자료형이 아닌 실제 종이사전) 단어를 찾고 싶을 때 쓰는 알고리즘과 굉장히 유사하다. 맨 앞에서 시작해서 순서대로 모든 항목을 확인하는 것이 아니라, 중간에서부터 시작해서 여러분이 찾고자 하는 단어가 그 앞에 오는지 뒤에 오는지를 확인하는 방법이다. 만약 앞에 온다면, 시퀀스의 앞 절반을 검색한다. 그렇지 않으면, 뒤쪽 절반을 검색한다. 어느 경우든 여러분은 남은 항목을 절반으로 줄일 수 있는 것이다.

만약 시퀀스에 1,000,000개의 항목이 들어있다면 여러분이 원하는 단어를 찾거나 그것이 들어있지 않다는 결론을 내리는 데까지 20단계 정도가 걸린다. 그러니까 선형검색보다 50,000배는 빠르다.

이미지 출처: http://www.tipssoft.com/bulletin/board.php?bo_table=FAQ&wr_id=69

내용 출처: 복잡계와 데이터 과학