Analysis of Algorithms | Asymptotic Analysis

읽기 전..

• 향후 상기한 제목으로 작성될 게시물은 모두 Geeks for Geeks Algorithms 페이지들을 번역 및 작성자의 해석대로 정리할 예정입니다.
• 정확한 이론 베이스는 당연히 없고 학습한 내용을 정리할 목적으로 가볍게 작성하였기 때문에 오개념이 있을 수 있으니 혹시 페이지를 방문하신 분들께서는 참고바랍니다.
• 개념을 바로잡기 위한 지적은 언제나 환영이니 부탁드립니다.

Algorithm Analysis? Performance?

흔히 알고리즘을 다룰 때 빠질 수 없는 개념은 '성능'이다. 성능이 보장되어 있어야 안정성, 보안 등 각종 이슈를 모두 해결할 수 있다. 알고리즘의 성능을 평가할 때는 단순히 '규모'에 대한 개념만 가지고 있으면 된다. 많은 양의 데이터를 정확하고 빠른 시간에 처리할 수 있는 알고리즘이 좋은 알고리즘이라고 생각하자.

단순하게 알고리즘 성능을 분석한다고 할 때 두 개의 알고리즘을 돌려서 적은 시간이 걸리는 알고리즘이 더 우수하다고 여겨진다. 그러나 적은 input부터 많은 input까지 고려하면 다음의 경우도 존재할 수 있다.

1. 일부 input에서는 1번이 우수하고 다른 input에서는 2번이 우수한 경우
2. 일부 input의 경우 어떤 기계에서는 1번이 우수하고, 다른 input의 경우 다른 기계에서는 2번이 우수한 경우

위 문제를 해결하기 위한 알고리즘 분석 개념 중 하나로 점근적 분석이 있다.

Asymptotic Analysis(점근적 분석)이란?

점근적 분석이란 알고리즘을 분석하기 위한 기법 중 하나로 input size대비 알고리즘이 처리하는 데 걸리는 시간(혹은 공간)에 대해 평가한다.

예를 들어, 빠른 머신에서 Linear Search를 수행할 때와 느린 머신에서 Binary Search를 수행할 때 일정 시점까지는 Linear Search가 빠르겠지만 input size가 점점 커질수록, 결국 Binary Search의 소요시간이 더 작아지는 시점이 온다.

• 뒤에 나오는 개념이지만 Linear Search의 시간복잡도는 n인 반면, Binary Search의 시간복잡도는 $\log n$이기 때문

그렇다고 점근적 분석이 정확한 알고리즘 성능을 제시하지는 않는다.

$1000nlog n$과 $2nlog n$은 일정범위에선 분명한 차이가 있지만 점근적 분석에 따르면 "$nlog n$"이므로 서로 동일한 성능을 가진다고 판단하는 문제가 있다.

게시물 출처: Analysis of Algorithms | Set 1 (Asymptotic Analysis)

Linear Search 알고리즘에 대해 분석하기

Linear Search 알고리즘을 적용할 때 3가지 케이스에 대해 분석하기로 한다.

def search(arr, n, x):
    for i in range(n):
        if arr[i]==x:
            return i
    return -1
#arr는 입력 list, n은 arr의 길이, x는 찾는 값

1. Worst Case

   서칭 알고리즘의 최악 케이스는 주어진 배열 내에 찾고자 하는 원소가 없어 모든 원소에 대해 탐색해야 하는 경우다. 특히, Linear Search의 경우 첫 번째 원소부터 하나씩 탐색하기 때문에 input size가 n이라면 최악의 경우의 시간복잡도는 Θ(n)이다.

2. Average Case

   일반적인 경우는 평균으로 해석하자고 가정하면 균일하게 분포된 모든 케이스에 대해 걸리는 탐색시간을 케이스의 수로 나누면 된다. 즉, 찾고자 하는 원소가 첫 번째에 위치한 경우부터 존재하지 않는 경우까지 모든 시간을 더한 뒤 경우의 수로 나눈 결과는 아래와 같다.
   $$
   \begin{align}
   Average\;Case\;Time &= \frac{\sum_{i=1}^{n+1}(\Theta(i))}{n+1}
   \\&=\frac{\Theta((n+1)\cdot(n+2)/2)}{n+1}
   \\&=\Theta(n)
   \end{align}
   $$

3. Best Case

   최상의 케이스는 찾고자 하는 원소가 첫 번째에 위치하여 한 번의 접근으로 탐색에 성공하는 경우로 시간 복잡도는 Θ(1)이다.

일반적으로 알고리즘을 분석할 땐 수행 시간의 상계(Upper bound)에 대한 정보를 제공할 수 있기에 가장 최악의 경우를 상정한다. 평균 케이스 분석은 모든 가능한 input에 대해 수학적으로 어떻게 분포되어 있는지 파악하고 있어야 하므로 잘 쓰이지 않는다.

다만 몇몇 알고리즘은 worst case와 best case 간의 소요시간이 동일한 경우가 있다. 예를 들어, Merge sort의 시간복잡도는 모든 케이스에 대해 Θ$(n\log n)$이다.

게시물 출처: Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)