1.2선형 탐색 알고리즘의 성능

선형 탐색 알고리즘의 성능은 if 문 실행 횟수(#1) 즉, 비교 연산 횟수를 성능의 기준으로 삼습니다. 그러면 비교 연산 횟수는 어떻게 구할까요? 대상 데이터가 리스트의 첫 번째 요소라면 한 번만 비교하면 됩니다. 하지만 대상 데이터가 리스트의 마지막 요소라면 리스트의 모든 데이터와 비교해야 합니다. 즉, 선형 탐색 알고리즘은 다음과 같은 특징을 갖습니다.

• 첫 번째 요소를 찾는 경우: 최선의 경우(Best Case)

• 마지막 요소를 찾는 경우: 최악의 경우(Worst Case)

대부분의 경우 최악의 경우를 계산합니다. ‘최악의 경우라도 몇 번의 연산 안에는 실행이 완료된다는 것을 보장’할 수 있기 때문입니다.

선형 탐색에서 최악의 경우는 대상 데이터가 리스트의 맨 마지막에 있는 경우입니다. 이때 if 문을 이용한 비교 횟수는 데이터 개수와 비례해서 증가합니다. 데이터 개수가 n일 때, 비교 횟수를 그래프로 표현하면 그림 15-1과 같습니다.

그림 15-1 선형 탐색일 때