#6-1 The Art of Computer Programming - 정렬과 검색

지난 장에 서 정렬을 끝내고 이번장은 검색에 대한 내용이다.

 

저자는 검색보다는 '정보의 저장과 조회'라는 이름이 더 나았을 수도 있다고 한다.

혹은 표 조회(Table Look-Up)이라고 부를 수도 있겠다.

대부분은 주어진 사실들에 빠른 조회가 가능한 방식으로 보존하고 조직화하는 게 중요하다.

 

모든 레코드 들의 모음을 표 or 파일 이라고 부르고

큰 파일 또는 파일들의 그룹을 데이터베이스라고 부른다.

 

검색에는 인수(찾을 수) K가 주어진다. 검색이 완료되었을 때는

1. K를 담을 유일한 레코드를 찾음으로서 검색 성공

2. K를 어디에서도 못찾아서 검색 실패

 

많은 프로그램들에서 시간을 가장 많이 소비하는 부분이 검색이다.

따라서 나쁜 검색 방법을 좋은 검색 방법으로 대체하면 프로그램 수행 시간을 크게 줄일 수 있다.

 

정렬을 내부/외부로 분류한 것과 같이, 검색도 내부/외부로 분류가 가능하다.

 

첫 번째 장에서는 가장 기초적인 '순차 검색'에 대해서 알아본다.

 

시작점에서 검색을 시작해서 찾는 키가 발견되면 멈추는 방법으로, 누구나 생각할 수 있는(혹은 처음 생각해내는) 방법이다.

검색에 대한 분석에 80-20법칙인 파레토의 법칙에 대한 설명도 나온다.

순차 검색을 뭔가 더 효율적으로 하는 방법을 소개하는데

나는 그게 무슨 의미인지 이해를 못함 ㅠㅠ 두세번 읽어봤는데도 모르겠어서 GG