Sehun Hu

Sehun Hu

I am a developer interested in developing interfaces that enable efficient human-computer communications.

알고리즘 성능 분석과 시간 복잡도

9 분 소요

도입(Introduction)

컴퓨팅 알고리즘들의 Performance(성능)를 어떻게 측정하는지에 대해 알아보도록 하자.

참고로 이번 글에서 다루는 내용은 머신러닝/딥러닝 알고리즘들은 제외한 일반적인 알고리즘들의 성능을 어떻게 분석하고 측정하는지에 대해 다룬다.

이 글은 알고리즘 문제 해결 전략 (구종만 지음)의 내용의 “2장 : 알고리즘 분석” 부분을 읽고 책에서 C++로 구현해놓은 코드들을 Python으로 새로 구현하고 일부 개념적인 내용들을 요약 및 정리한 글임을 밝힙니다.

알고리즘을 평가하는 두 가지 기준

한 문제를 해결하기 위해 여러 개의 알고리즘이 있다고 할 때, 어떤 알고리즘이 가장 적합한 알고리즘인지를 어떻게 알 수 있을까?

알고리즘을 평가하는 가장 큰 두 가지의 기준은 다음과 같다.

  • 시간 : 적은 시간을 사용하는 알고리즘은 더 빠르게 동작한다는 의미
  • 공간 : 적은 공간을 사용하는 알고리즘은 더 적은 용량의 메모리를 사용한다는 의미

이 두가지의 기준은 서로 충돌하는 경우가 많다. 예를 들어, 동적 계획법이 한 가지 예인데, 동적 계획법은 메모리를 더 많이 사용해서 알고리즘의 수행 속도를 높이도록 한다.

알고리즘 평가 기준 : 시간

여러 알고리즘들의 성능을 시간을 통해 측정한다고 할 때, 가장 쉬운 방법은 프로그램의 수행 시간을 측정하는 것이다.

하지만 프로그램의 실행 시간을 측정하는 방법은 다음과 같은 이유들로 인해 성능 지표로 사용되기에는 어려움이 있다.

  • 프로그램의 수행 시간은 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등의 다양한 요소에 의해 바뀔 수 있음
  • 프로그램의 실제 수행 시간은 다양한 입력(입력의 개수, 특성 등)을 반영하지 못함

한편, 알고리즘의 수행 시간은 반복문이 수행되는 횟수를 통해 결정되는 경우가 많다.

또한 반복문은 입력의 개수에 따라 수행 횟수가 결정된다.

따라서, 대부분의 경우에서 알고리즘의 수행 시간은 반복문이 수행되는 횟수로 측정하며 반복문의 수행 횟수는 입력의 개수와 관계있으므로 입력의 개수에 대한 함수로 표현한다.

다음에 나오는 코드들은 0 이상의 정수의 원소들로 구성된 리스트에서 가장 많이 등장하는 수를 찾는 코드들이다.

또한, 아래에는 각 알고리즘들의 아이디어와 수행 시간을 적어두었다. (입력 배열의 크기를 N이라고 하였다.)

from typing import List

def majority1(A: List[int]):
    majority = -1
    majorityCount = 0

    for i in A: # 첫번째 반복문
        V = i
        count = 0

        for j in A: # 두번째 반복문
            if j == V:
                count = count + 1

        if count > majorityCount:
            majorityCount = count
            majority = V

    return majority
  • Idea : 중첩 반복문을 돌면서 각 원소들의 빈도를 측정, 이중 for문을 통과한 후에 최대 빈도수를 갱신한다.
  • 첫번째 반복문의 수행 횟수 : $N$번
  • 두번째 반복문의 수행 횟수 : $N^2$번
  • 알고리즘의 수행 시간 : $N^2$번 (N번은 무시)
from typing import List

def majority2(A: List[int]):
    counts = [0 for i in range(0, max(A)+1)]

    for i in A: # 첫번째 반복문
        counts[i] = counts[i] + 1

    majority = 0
    for i in A: # 두번째 반복문
        if counts[i] > counts[majority]:
            majority = i

    return majority
  • Idea : 각 원소의 출현 빈도를 counts라는 리스트에 저장하고 이 리스트를 순회하면서 최대 빈도수를 찾는다.
  • 첫번째 반복문의 수행 횟수 : $N$번
  • 두번째 반복문의 수행 횟수 : $N$번
  • 알고리즘의 수행 시간: $N$번 (2N이지만 2는 무시)

위와 같이 알고리즘은 수행 시간의 형태에 따라 여러 가지 유형으로 나눌 수 있으며 그에 따라 알고리즘 효율성을 분석할 수 있다.

추가적으로 알고리즘에 따라, 입력으로 주어지는 데이터의 개수가 아닌, 입력 숫자의 크기에 따라 수행 시간이 달라지기도 한다. ex) 소인수분해 알고리즘

수행 시간에 따른 알고리즘의 분류

  • 상수 시간 알고리즘
  • 선형 시간 알고리즘
  • 선형 이하 시간 알고리즘
  • 다항 시간 알고리즘
  • 지수 시간 알고리즘

상수 시간 알고리즘

언제나 같은 시간이 걸리는 알고리즘을 의미한다.

즉, 입력의 개수에 상관없이 언제나 같은 시간이 걸리는 알고리즘들을 상수 시간 알고리즘이라 한다.

(뒤에 나올 시간 복잡도로 표현하면 $O(1)$의 수행 시간을 갖는다고 한다.)

선형 시간 알고리즘

선형 시간 알고리즘은 수행 시간이 입력의 개수 $N$에 정비례하는 알고리즘들을 의미한다.

즉, 이러한 알고리즘들은 $N$이 두 배 커지면 실행도 두 배 오래 걸리고, $N$이 반으로 줄어들면 수행 시간도 반으로 줄어든다.

예시)

def movingAverage(A, M):
    ret = []
    partialSum = 0

    for i in range(0, M-1):
        partialSum += A[i]

    for i in range(M-1, len(A)):
        partialSum += A[i]
        ret.append(partialSum / M)
        partialSum -= A[i-M+1]
    
    return ret

위의 코드는 이동 평균을 구하는 코드인데, 윈도우 단위로 이동하면서 윈도우를 벗어나는 값은 빼주고 윈도우에 새로 들어온 값은 더해주는 방식으로 각 지점의 이동 평균을 구한다.

윈도우의 크기를 $M$이라 할 때, 첫번째 반복문은 $M-1$의 수행 시간을 갖고 두번째 반복문은 $N-M+1$의 수행 시간을 가져, 최종적으로는 $M-1+(N-M+1)=N$의 수행 시간을 갖는다.

선형 시간에 실행되는 알고리즘들은 대개 우리가 생각할 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.

(선형 시간 알고리즘들은 모든 데이터를 한번씩만 보면 된다고 생각하면 됨)

선형 이하 시간 알고리즘

선형 이하 시간 알고리즘은 입력의 개수가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 의미한다.

대표적인 예로는 이진 탐색 알고리즘이 있다.

[이진 탐색 알고리즘의 대략적인 과정]

  1. 어떠한 순서로 정렬한다.
  2. 정렬된 순서에서 절반을 나누어 원하는 것이 있는지 판단한다.(또는 크기를 비교한다.)
  3. 타겟이 되는 절반을 선택한다.
  4. 이 과정을 반복한다.

[이진 탐색 알고리즘의 수행 시간] 입력 개수 $N$에 의한 수행 시간 : $log_2N$ —> 보통 $logN$으로 표시 예시) $N=100,000$일 경우, $log_{2}100,000=16$번이면 원하는 값을 찾을 수 있음

선형 이하 시간 알고리즘은 선형 시간 알고리즘보다도 속도가 더 빠른 알고리즘들이다.

다항 시간 알고리즘

수행 시간이 $N$과 $N^2$, 그 외의 N의 거듭제곱들의 선형 결합으로 이루어지는 다항식으로 표현되는 알고리즘들이다.

예시) $N$, $N^2$, $N^6$, $N^{100}$

선형 시간 알고리즘도 다항 시간 알고리즘의 하나이다.

지수 시간 알고리즘

수행 시간이 $2^N$과 같이 $N$이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들이다.

지수 시간 알고리즘들은 가장 큰 수행 시간이 걸리는 알고리즘들로 입력의 개수가 늘어날 수록 다항 시간과는 비교도 안 되게 빠르게 증가한다.

대표적으로는 다음과 같이 피보나치 수열을 재귀를 통해 구현한 알고리즘이 지수 시간 알고리즘을 가진다.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

위의 코드는 $2^{\frac{N}{2}}$의 수행 시간이 걸린다고 알려져있다.

자세한 증명은 다음의 블로그를 참고하기 바란다.

[Algorithm] 피보나치 수열과 시간복잡도

시간 복잡도

시간 복잡도는 가장 널리 사용되는 알고리즘의 수행 시간 기준이다. 시간 복잡도의 정의는 다음과 같다.

시간 복잡도 : 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대해 함수로 표현한 것

기본적인 연산은 더 작게 쪼갤 수 없는 최소 크기의 연산이라고 생각하면 된다.

즉, 기본적인 연산은 중첩된 반복문의 가장 내부에 있는 기본적인 연산들( ex. 사칙연산, 대소 비교, 변수 대입 등)을 의미한다.

시간 복잡도가 높다는 말은 입력의 개수가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 것을 의미한다.

즉, 시간 복잡도가 낮다고 해서 항상 더 빠르게 동작하는 것은 아니다.

예를 들어, A 알고리즘이 $10240+35logN$의 시간 복잡도를 갖고, B 알고리즘이 $2N^2$의 시간 복잡도를 갖는다고 할 때, A 알고리즘은 $logN$의 영향이 거의 없기에 사실상 선형 알고리즘이라고 볼 수 있다. 또한 B 알고리즘은 전형적인 다항 시간 알고리즘이다.

대략적으로 $N$이 70이하일 경우, A 알고리즘의 속도가 더 느리고 $N$이 70이상이 될 때부터 A 알고리즘의 속도가 더 빨라진다.(실제로 그래프를 그려보기 바란다.)

즉, A 알고리즘은 입력의 개수가 작더라도 더 빨라지지 않지만 B의 경우에는 입력의 개수가 작으면 더 빨라지고 입력의 개수가 커지면 속도가 급격하게 느려진다.

이러한 의미에서 시간 복잡도는 알고리즘의 속도를 측정하기 위한 완벽한 기준은 아니다. 즉, 문제에서 해결할 입력의 개수가 매우 작을 경우 시간 복잡도는 큰 의미를 가지지 못할 수도 있다.

최선/최악/평균 수행 시간

알고리즘의 수행 시간은 항상 입력의 개수에만 영향을 받는 것은 아니다.

예를 들어, 어떤 배열에서 특정 원소를 찾는 문제를 푸는 알고리즘의 경우, 특정 원소가 존재하는 위치에 따라 시간이 덜 걸릴수도 있고 더 걸릴수도 있다. 즉, 운 좋게 특정 원소를 한 번에 찾을수도 있고 운이 나쁘게 거의 모든 원소들을 확인해본 후에야 찾을 수도 있기 때문이다.

따라서, 알고리즘이 해결하고자 하는 문제 또는 입력의 형태에 따라 수행 시간이 달라지는 경우도 고려해야 한다.

이러한 문제를 고려하기 위해서 우리는 최선/최악의 경우, 그리고 평균적인 경우데 대한 수행 시간을 따로 계산한다.

다음과 선형 탐색 코드에서 최선/최악/평균 수행 시간에 대해 계산해보자.

def search(target_list, element):
    for idx, current_target in enumerate(target_list):
        if current_target == element:
            return idx
    return -1
  • 최선의 수행 시간 : 찾으려는 원소가 리스트의 맨 앞에 있을 때 알고리즘은 한 번 수행된다. 따라서 이 경우 반복문의 수행 횟수는 1이므로 수행 시간은 1이다.
  • 최악의 수행 시간 : 리스트에 해당 원소가 없을 때 알고리즘은 $N$번 반복하고 종료된다. 따라서 이 경우 반복문의 수행 횟수는 $N$이므로 수행 시간은 $N$이다.
  • 평균적인 경우의 수행 시간 : 평균적인 경우의 수행 시간을 분석하기 위해서는 존재할 수 있는 모든 입력의 등장 확률이 모두 같다고 가정해야 한다. 만약 주어진 배열이 항상 찾는 원소를 포함한다고 가정하면 반환 값의 기대치는 대략적으로 $\frac{N}{2}$이 되고 평균적인 수행 시간도 $\frac{N}{2}$이 된다.

이 세 가지 기준 중에서 보통적으로 사용하는 것은 최악의 수행 시간 혹은 평균 수행 시간이다. 많은 경우, 이 두 기준은 따로 구분되지 않고 쓰이는데, 여러 알고리즘에서 이 두 기준이 거의 같기 때문이다.

빅오 표기법(Big-O Notation)

시간 복잡도는 알고리즘의 수행 시간을 표기하는 방법이지만, 계산하기 너무 힘들다는 문제가 있다.(알고리즘의 필요 명령어 수라는 것이 모호할 뿐만 아니라, 알고리즘이 복잡할 때 그것을 한줄씩 세는 것도 힘들다.)

따라서 수행 시간을 따질 때 가장 깊이 중첩된 반복문의 수를 고려했던 것처럼 빅오 표기법은 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시한다.

또한, 빅오 표기법은 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버린다.

빅오 표기법의 예시)

  • $N$ —> $O(N)$
  • $NM2^M$ —> $O(NM2^M)$
  • 42 —> $O(1)$
  • $2^NM$ —> $O(2^NM)$
  • $\frac{1}{64}N^2M+64NM$ —> $O(N^2M)$
  • $N^2M+NlogM+NM^2$ —> $O(N^2M+NM^2)$

위의 5, 6번째 예시들처럼 알고리즘의 입력의 개수가 두 개 이상의 변수로 표현될 때는 그중 가장 빨리 증가하는 항들만을 떼놓고 나머지를 버린다.

빅오 표기법의 의미는 함수의 상한이다.

이에 대해서는 인생의 로그캣 블로그 : 빅오 표기법(big-O notation)이란 에서 빅오 표기법의 수학적 정의에 대한 내용을 읽으면 이해할 수 있다.

요약해서 설명하자면 빅오 표기법은 어떠한 최악의 경우에도 알고리즘의 시간은 점근 상한선인 $k*g(n)$을 넘을 수 없다. 따라서, 빅오 표기법은 “대략적으로 알고리즘이 이정도 시간보다는 빠를 수는 없어”라는 의미가 된다.

빅오 표기법 성능비교 그래프

big_o_graphs.png

수행 시간 어림짐작하여 알고리즘 선택하기

시간 복잡도를 통해 알고리즘의 수행 시간을 완벽히 예측할 수는 없다.

하지만 코딩 테스트나 여러 알고리즘 대회에서는 수행 시간에 대한 제한 시간을 준다.

따라서 알고리즘의 수행 시간을 어림짐작하여 제한 시간을 초과할지를 확인하고 이를 통해 어떤 알고리즘을 선택할지를 결정할 수 있어야 한다.

다음과 같은 방법으로 알고리즘의 수행 시간이 제한 시간을 초과하는지 따진다.

입력의 최대 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수가 1억($10^8$)을 넘어가면 수행 시간이 1초를 넘어설 가능성이 크다.

위와 같은 방식으로 알고리즘의 수행 시간을 어림짐작하면 거의 대부분의 대회나 코딩 테스트에서 적용 가능할 것이다.

예시) $O(N^3)$, $O(N^2)$, $O(NlogN)$, $O(N)$ 알고리즘이 있다고 할 때, 입력의 개수(크기) $N$에 대해 제한 시간 1초를 넘어서는 알고리즘을 걸러내보자.

  • $N = 1,000$ : $O(N^3)$ 알고리즘의 반복문 수행 횟수는 10억을 넘어서기 때문에 제한 시간 1초를 넘어설 가능성이 크다. 반면 다른 세 개의 알고리즘들은 별 무리 없이 수행할 수 있다.
  • $N = 10,000$ : $O(N^3)$ 알고리즘의 반복문 수행 횟수는 1조이므로 제한 시간 1초를 거의 무조건 넘어설 것이다. 반면, $O(N^2)$ 알고리즘은 수행 횟수가 1억이므로 주의해야할 범위에 들어간다. 다른 알고리즘들은 무리 없이 수행할 수 있다.
  • $N = 100,000$ : $O(N^3)$ 알고리즘은 무조건 제한 시간 안에 수행 불가능하다. $O(N^2)$ 알고리즘도 수행 횟수가 100억이므로 돌아갈 가능성이 높지 않다. 반면, $O(NlogN)$ 알고리즘은 대략 2천만 정도이므로 수행 가능하며 $O(N)$도 마찬가지로 수행 가능하다.

위의 예시와 같이 알고리즘의 수행 시간을 어림짐작하여 어떤 알고리즘을 사용할지를 결정할 수 있다.

또한, 1억이라는 기준은 상당히 보수적으로 정한 것이기 때문에 거의 대부분의 대회에서 적용 가능하고 실제로 1억을 넘어서지만 1초 안에 동작할 가능성도 많다.

따라서, 어느정도 어림짐작이라는 것을 생각하여야 하며 반복문 내부가 얼마나 복잡한지, 시간 복잡도 분석 과정에서 생략된 상수 등에 의해서 수행 시간이 더 줄어들 수도 있음을 이해하고 있어야 한다.

재귀 알고리즘의 시간 복잡도 계산

재귀 알고리즘의 시간 복잡도를 계산하는 것은 쉽지 않은 일이다.

하지만 마스터 정리(Master Theorem)이라는 것을 사용하면 재귀 알고리즘의 수행 시간을 빅 오 표기법으로 쉽게 표현할 수 있다.

다음과 같은 블로그에 마스터 정리가 잘 설명되어 있다.

마스터 정리 Master Theorem 알고리즘 시간 복잡도 구하기

알고리즘 평가 기준 : 공간

알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 말이다.

알고리즘에서는 속도와 공간이 서로 상충하는 경우가 많다.

즉, 어떤 알고리즘은 더 많은 메모리를 사용해 수행 속도를 높히는 알고리즘도 있고 반면에 수행 속도는 낮아지더라도 메모리 사용량을 적게 하는 알고리즘도 있다.

프로그래밍 대회에서 주로 중요시되는 알고리즘의 기준은 속도이므로 공간에 대해서는 여기까지만 언급만 하고 넘어가겠다.

저자

참조

댓글남기기