2알고리즘 분석

 

순차 탐색 알고리즘으로 원하는 값을 찾으려면 비교를 몇 번 해야 할까요? 이 질문은 답하기가 약간 모호합니다. 왜냐하면 경우에 따라 다르기 때문입니다. 찾는 값이 리스트의 맨 앞에 있다면 단 한 번만 비교해도 결과를 얻을 수 있습니다. 하지만 찾는 값이 리스트의 마지막에 있거나 아예 없다면 리스트의 끝까지 하나하나 비교해야 합니다.

이처럼 경우에 따라 계산 횟수가 다를 때는 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 각각 계산 복잡도를 생각해 보기도 합니다. 물론 어느 경우든 나름대로 의미가 있지만, 최악의 경우를 분석하면 어떤 경우라도 그보다는 빨리 계산할 수 있을 것입니다. 따라서 보수적인 관점에서 이 알고리즘을 최악의 경우로 분석해 보면 비교가 최대 n번 필요하고 계산 복잡도는 O(n)입니다.

즉, 순차 탐색으로 스무 개의 자료 중에서 어떤 값을 찾으려면 비교를 최대 스무 번 해야 하고, 백 개의 자료라면 비교를 최대 백 번 해야 합니다. 십만 개의 자료 중에 특정 값을 찾아야 한다면 어떨까요? 얘기를 조금 바꿔 십만 단어가 수록된 국어사전에서 어떤 단어를 찾기 위해 사전의 첫 장부터 차례로 십만 번 단어를 비교해야 한다거나, 우리나라 국민 한 명을 주민등록번호로 찾기 위해 주민등록번호를 오천만 번 비교해야 한다면 어떨까요? 자료 한 개를 찾는 데 엄청난 횟수의 비교가 필요하다는 사실이 이제 감이 올 것입니다.

하지만 다행히도 우리는 사전의 첫 장부터 한 장씩 넘기면서 원하는 단어를 찾지 않습니다. 사전의 단어는 가나다순 혹은 알파벳순으로 ‘정렬’되어 있기 때문입니다. 다음 장에서는 정렬을 배워 보겠습니다.