순차탐색과 시간복잡도

본 포스트는 윤성우님의 열혈 자료구조를 출처로 작성된 글입니다.
필자의 복습이 주 목적이며, 오타나 잘못된 내용이 발견될 시 답글로 남겨주시면 감사하겠습니다.

시간복잡도

시간복잡도의 이해를 위해 간단한 알고리즘인 순차탐색 알고리즘의 시간복잡도를 알아보자.
이하에서 언급되는 순차탐색은 배열을 기반으로 하고 있다.

핵심이 되는 연산

우선 알고리즘의 시간복잡도를 판단하기 위해서는 핵심이 되는 연산을 찾아야 한다.

한가지 팁은 다른 연산자에 의존적이지 않은 연산자, 즉 독립적인 연산자 중에서 다른 연산자들이 가장 많이 의존하는 연산자를 찾는 것이다.
핵심적인 연산자는 본인의 결과가 다른 연산자들의 연산횟수를 결정하기 때문이다.

최악의 경우

또한 시간복잡도를 계산할때는, 일반적으로 해당 알고리즘의 최악의 경우를 고려한다.
순차 탐색의 경우 최선의 경우는 연산횟수 1번만에 대상을 탐색하는 것지만, 최악의 경우에는 배열의 길이인 $n$번 연산을 진행해야 한다.

왜 평균적인 경우(Average case)가 아니라 최악의 경우를 따지는가?
무엇이 평균인가? 이는 결정하기 매우 어려운 문제이다. 가령... 다음의 질문이 따라올 수 있다.

1. 평균적인 경우를 어떻게 결정할 것인가?
2. 그 경우가 평균적임을 어떻게 증명하는가?
3. 평균적인 경우의 환경은 어떻게 구성할 것인가? 평균적인 환경의 평균적인 환경... 등등?

최악의 경우는 최소한 결정가능하다. 따라서 우리는 알고리즘 평가에 일반적으로 최악의 경우를 활용한다.

순차탐색의 시간복잡도

최악의 경우

순차탐색 알고리즘에서 핵심이 되는 연산은 바로 비교연산==이다.
이때 시간복잡도는 위에서 언급했듯이, $n$이다. 따라서 빅오는 (최악의 경우) $O(n)$이다.

평균적인 경우

일반적으로 알고리즘의 평균적인 경우를 판단하지 않지만, 순차탐색정도면 못해볼만한 것도 아니다.

이를 판단하기 위해선 몇 가지 가정이 필요하다. 이는 평균의 환경 조성을 위해서다. 물론 이 가정들하에서 이뤄지는 순차탐색이 순차탐색 알고리즘의 객관적 평균임을 담보하진 않는다.

1. 탐색 대상이 배열에 존재하지 않을 확률은 50%이다.
2. 배열 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.

이제 다음과 같이 케이스를 구별하자.

1. 배열내에 탐색 대상이 존재하지 않을 경우 가정 2에 의해($1\over2$확률)로 $n$번의 탐색을 진행한다.

2. 배열내에 탐색 대상이 존재할 경우 가정 2에 의해 ($1\over2$확률)

   2.1 길이가 $n$인 배열에서, 1번째 인덱스에 타겟이 있을 경우, 1번의 탐색으로 타겟을 찾는다.

   2.2 길이가 $n$인 배열에서, 2번째 인덱스에 타겟이 있을 경우 2번의 탐색으로 타겟을 찾는다.

   2.3 길이가 $n$인 배열에서, $n$번째 인덱스에 타겟이 있을 경우 $n$번의 탐색으로 타겟을 찾는다.

   2.4 가정1에 의해 탐색 대상이 배열 전체 인덱스에 존재할 확률은 동일하므로, 우리는 탐색 대상이 어디에 있던간에 상관없이 모든 경우를 고려할 수 있다. 전체 탐색횟수는 $n \times n$이고, 타겟을 찾을때의 탐색횟수는 $1+2+3...+n$이다. 따라서

   ${타겟을 찾았을때의 탐색횟수 \over 전체 탐색횟수} \approx {1 \over 2}$

   이다.

3. 따라서 순차탐색에서 몇가지 가정 하 평균적인 경우의 시간복잡도는 다음과 같다.

   $T(n) = n \times {1 \over 2} + {n \over 2} \times {1 \over 2} = {3 \over 4}n$