알고리즘 분석의 실례 (Big-Oh Notation 실례)

이전에 알아봤던 Big-Oh Notation 의 실례들을 살펴보자.

$O(1)$

파이썬의 list 클래스에서는 각 리스트의 길이를 저장하고 있는 변수가 존재하여 리스트 요소 하나하나를 반복적으로 접근하여 세지 않고도 그 길이를 즉각 반환하여 준다. 이런 측면에서 본다면 리스트의 길이를 구하는 것은 $O(1)$ 에 해당된다고 할 수 있다. 또한 파이썬의 리스트는 array-based sequences 로 실행되기 때문에 각각의 요소들은 연속적인 저장 공간에 하나씩 저장이 되고, 이들은 모두 인덱스를 이용하여 직접 접근할 수 있다. 예를 들어, input_data[i] 라고 하면 input_data 라는 리스트의 인덱스 i 인 저장소의 값을 그대로 반환해 준다. 따라서 이것 역시 $O(1)$ 에 해당된다고 할 수 있다.

$O(\log n)$  

Big-Oh Notation 에서 봤었던 find_max 함수를 기억하는가? 

def find_max(input_data):
    maximum = input_data[0]
    for element in input_data:
        if element > maximum:
            maximum = element
    return maximum

위 코드에서 maximum 에 input_data[0] 이 할당된 이후로 maximum 값은 몇 번이나 그 값이 바뀌게 될지에 대해 생각해 볼 필요가 있다. 즉, maximum = element 라는 부분이 몇 번이나 실행될까를 생각해 보자. input_data 의 요소들이 오름차순으로 정렬되어 있다면 당연히 $n-1$ 번 그 값이 새롭게 업데이트 될 것이다. 하지만 요소들이 임의의 순서로 나열되어 있다면 maximum 값이 새롭게 업데이틑 되는 횟수의 기댓값은 어떻게 될까? maximum 값이 새롭게 업데이트 되려면 현재 요소가 이전에 나왔던 모든 요소들 보다 큰 값을 가져야 한다. 만약 $n$ 개의 요소가 모두 서로 다른 값들을 갖는다면 $j$ 번째 요소가 처음 $j$개 요소 중 최댓값을 갖게 될 확률은 $\dfrac{1}{j}$ 이 되고, 처음에 maximum 이 input_data[0] 으로 초기화 된 것까지 포함하여 maximum 값이 새롭게 업데이트 되는 횟수의 기댓값은 $H_n = \sum \limits_{j=1}^n \dfrac{1}{j}$ 이 된다. (이것은 조화수열의 합과 같기 때문에 $n^{th}$ harmonic number 라 부르고 $H_n$ 으로 표기하는 것이다.) 

그런데 만약 $n=2^k$ ($k \ge 2$ 인 자연수)으로 주어진다고 한다면 $$\begin{split} H_n &=\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \dfrac{1}{6} + \dfrac{1}{7} + \dfrac{1}{8} + \cdots + \dfrac{1}{2^k -1} + \dfrac{1}{2^k} \\ &< \dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{8} + \cdots + \dfrac{1}{2^{k-1}} + \dfrac{1}{2^k} \end{split}$$ 이 성립하게 된다. 위 식에서 제2행은  $\dfrac{1}{2^m}$ 부터 $\dfrac{1}{2^m-1}$ 까지의 모든 값을 $\dfrac{1}{2^m}$ 으로 바꾼 것인데, 이 범위안에 속한 모든 값들은 모두 $\dfrac{1}{2^m}$ 보다는 작거나 갖게 된다. 예를 들어, $\dfrac{1}{2^2}$ 부터 $\dfrac{1}{2^3-1}$ 까지의 값을 보면 $\dfrac{1}{5} < \dfrac{1}{4}$,   $\dfrac{1}{6} < \dfrac{1}{4}$,   $\dfrac{1}{7} < \dfrac{1}{4}$ 이기 때문에 부등호 관계가 성립하게 된다. 이것을 다시 정리하면  $$\begin{split} H_n &=\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \dfrac{1}{6} + \dfrac{1}{7} + \dfrac{1}{8} + \cdots + \dfrac{1}{2^k -1} + \dfrac{1}{2^k} \\ &< \dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{8} + \cdots + \dfrac{1}{2^{k-1}} + \dfrac{1}{2^k} \\ &= \dfrac{1}{1} + 2 \times \dfrac{1}{2} + 4 \times \dfrac{1}{4} + \cdots + 2^{k-1} \times \dfrac{1}{2^{k-1}} + \dfrac{1}{n} \\ &= k + \dfrac{1}{n} = \log_2 n + \dfrac{1}{n}\end{split}$$ 이때, $\dfrac{1}{n}$ 은 $n$ 의 값이 커짐에 따라 감소하게 되고,  $log_2 n$ 은 $n$ 의 값이 커짐에 따라 증가하기 때문에 우리는 $log_2 n$ 에 집중해야 하고, 따라서 $H_n$ 은 $O(\log n)$ 이 된다.

$O(n)$

다시 find_max 를 보도록 하자. 앞서 우리는 find_max 에서 가장 중요한 부분이 for-loop 이고 , for-loop 는 input_data의 크기인 $n$ 회 반복되므로 $O(n)$ 에 해당된다고 했었다. 그런데 좀 더 세밀하게 살펴보면 for-loop 가 $n$ 회 반복된다는 것은 if 문도 $n$ 회 반복하여 실행된다는 것이고, maximum = element 부분은 앞에서 살펴본 대로 평균적으로 $H_n$ 만큼 실행된다는 것을 알 수 있다. 즉, for-loop 자체는 $O(n)$ 에 해당되고, maximum = element 부분은 $O(\log n)$ 에 해당되지만, 이 경우에는 가장 최악의 상황에서 $O(n)$ 의 성능을 보장할 수 있기 때문에 find_max 는 $O(n)$ 이 되는 것이다.

$O \left ( n^2 \right )$

$n$ 개의 요소를 포함하고 있는 리스트 $S$가 있다고 해 보자. 우리는 똑같은 크기의 리스트 $A$ 를 만들어야 하는데 리스트 $A$ 의 각각의 요소는 다음과 같이 결정된다. $$A[j] = \dfrac{\sum \limits_{i=1}^j S[j]}{j+1}$$ 즉, $A[j]$ 에 해당하는 요소는 $A[0]$ 부터 $A[j]$ 까지의 산술평균이 된다는 뜻이다. 이를 위해서 다음과 같은 파이썬 코드를 작성했다고 해 보자.

def average(S):
    n = len(S)
    A = [0] * n
    for j in range(n):
        total = 0
        for i in range(j+1):
            total += S[i]
        A[j] = total / (j+1)
    return A

위 코드를 하나씩 분석해 보면

• n = len(S) 는 앞서 살펴봤듯이 $O(1)$ 에 해당된다.
  

• A = [0] * n 의 경우 모든 요소가 $0$ 인 크기 $n$ 인 리스트를 만드는 과정이므로 내부적으로는 $n$ 회 반복적인 작업이 일어나고 따라서 $O(n)$ 에 해당된다. 

• 위 코드에는 두 개의 for-loop 가 중첩되어 등장하는데, 먼저 바깥쪽 for-loop 를 보자. $j=0$ 에서 $j=n-1$ 까지 for-loop 가 반복되므로 이는 $O(n)$ 에 해당된다고 할 수 있다.

• 안쪽 for-loop는 어떨까? 안쪽 for-loop 의 경우 $j=0$ 에서 $j=n-1$ 로 바뀌는 동안 순차적으로 $1$회, $2$회, $3$회, $\cdots$, $n$ 회 반복된다. 즉, 최종적으로는 $1+2+3+\cdots +n = \dfrac{n}{(n+1)}{2}$ 회 반복되는 것이다. 따라서 $O \left ( n^2 \right )$ 에 해당된다.

이와 같은 사실을 바탕으로 위 코드는 $O \left ( n^2 \right )$ 이 된다는 결론을 내릴 수 있다.

여기서 잠깐!!!

만약에 위와 똑같은 작업을 하는 코드를 다음과 같이 작성했다면 어떻게 될까?

def average2(S):
    n = len(S)
    A = [0] * n
    total = 0
    for j in range(n):
        total += S[j]
        A[j] = total / (j+1)
    return A

먼저 for-loop 가 중첩되지 않았다는 것을 알 수 있고, 이전과는 다르게 total += S[j] 가 $n$ 회 반복되는 것으로 문제가 해결되는 것을 볼 수 있다. 따라서 위의 코드는 $O(n)$ 이 된다.

$O \left ( n^3 \right )$

원소의 개수가 모두 $n$ 개인 집합 $A, \; B, \; C$ 가 있다고 하자.  세 집합 모두에 속하는 공통된 원소가 있는지 없는지 체크하는 코드를 작성한다고 해 보자. 즉, $A \cap B \cap C = \emptyset$ 이면 True 를 반환하고, 그렇지 않으면 False 를 반환하는 것이다. 이를 위해 아래와 같은 코드를 작성하였다. 여기서는 $A, \; B, \; C$ 를 리스트로 나타내었다.

def disjoint(A, B, C):
    for a in A:
        for b in B:
            for c in C:
                if a == b == c:
                    return False
    return True

이제 딱 감이 오겠지만, 위 코드는 $O \left (n^3 \right )$ 에 해당된다. 그렇지만 아래와 같이 코드를 작성한다면 $O \left (n^2 \right )$ 가 된다.

def disjoint2(A, B, C):
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    if a == c:
                        return False
    return True

이 경우 바깥쪽 2개의 for-loop 는 반드시 실행이 되지만, 안쪽 for-loop 는 a==b 라는 조건을 만족시켰을 때만 실행이 되므로 $O \left (n^2 \right )$ 이라고 할 수 있는 것이다. 

일단 간단한 예제들은 여기까지 보도록 하고, 좀 더 복잡합 예제들은 알고리즘을 하나씩 공부해 나가면서 보기로 하자.