검색 알고리즘

빠른 정보 검색을 가능케 하는 자료 구조의 하나인 해시 테이블의 시각적 표현.

컴퓨터 과학에서 검색 알고리즘(search algorithm)은 이름 그대로 검색 문제를 해결하는 어떠한 알고리즘이라도 해당되며, 연속 변수나 이산 변수를 사용하여, 일부 데이터 구조 안에 저장된 정보를 검색하거나 문제 도메인의 검색 공간에서 계산을 하기 위해 사용된다. 검색 알고리즘이 쓰이는 부문은 다음을 포함한다:

위의 내용과 웹 검색에 기술되는 고전적인 검색 문제들은 모두 정보 검색의 문제들이지만 일반적으로 별도의 하위 분야로서 연구되며 다르게 해결되고 평가된다. 고전적인 검색 알고리즘들은 일반적으로 얼마나 빨리 해결책을 찾을 수 있는지, 해당 해결책이 최적임을 보장하는지의 여부를 평가한다. 정보 검색 알고리즘이 빨라야 하지만 좋은 결과가 남아있는지, 나쁜 결과가 포함되었는지 등에 대한 순위의 품질이 더 중요하다.

적절한 검색 알고리즘은 검색 대상이 되는 데이터 구조에 따라 달라질 수 있으며 데이터에 관한 이전 지식이 포함될 수도 있다. 일부 데이터베이스 구조는 특히 검색 알고리즘을 더 빠르고 더 효율적으로 만들기 위해 구성되는데, 이를테면 검색 트리, 해시 맵, 데이터베이스 인덱스가 있다.[1][2]

검색 알고리즘은 또한 검색 구조에 따라서도 분류가 가능하다. 순차 검색 알고리즘은 대상 키와 관련된 대상에 대해 모든 레코드를 선형 방식으로 검사한다.[3] 이진/반 정수 검색 알고리즘은 검색 구조의 중심을 대상으로 하고 검색 공간을 절반으로 분리시킨다. 비교 검색 알고리즘은 대상 레코드가 발견될 때까지 키 비교에 기반하여 레코드를 연이어 제거함으로써 선형 검색을 개선시키며, 정의된 순서가 있는 자료 구조에 적용이 가능하다.[4] 디지털 검색 알고리즘은 숫자 키를 사용하는 자료 구조에서 숫자의 속성에 기반하여 동작한다.[5] 끝으로, 해싱(hashing)은 해시 함수에 기반하여 키를 레코드에 직접 매핑시킨다.[6] 선형 검색 밖의 검색은 데이터가 특정 방식으로 정렬될 것이 요구된다.

알고리즘은 자신들만의 계산 복잡도나 이론적 최대 실행 시간에 의해 평가된다. 예를 들어 이진 검색 함수는 O(log n)(또는 로그 함수)의 최대 복잡도를 지닌다. 즉, 검색 대상을 찾는데 필요한 조작의 최대 수는 검색 공간 크기의 로그 함수이다.

참고문헌편집

인용편집

  1. Beame & Fich 2002, 39쪽.
  2. Knuth 1998, §6.5 ("Retrieval on Secondary Keys").
  3. Knuth 1998, §6.1 ("Sequential Searching").
  4. Knuth 1998, §6.2 ("Searching by Comparison of Keys").
  5. Knuth 1998, §6.3 (Digital Searching).
  6. Knuth 1998, §6.4, (Hashing).

서적편집

문헌편집

  • Schmittou, Thomas; Schmittou, Faith E. (2002년 8월 1일). “Optimal Bounds for the Predecessor Problem and Related Problems”. 《Journal of Computer and System Sciences》 65 (1): 38–72. doi:10.1006/jcss.2002.1822. 

외부 링크편집