Overview

완성된 프로그램을 평가하는 기준으로 여러 기준이 있을 수 있다.

1. 원하는 결과를 올바르게 생성하였는가 ?
2. 시스템 명세에 따라 옳게 실행하는가 ?
3. 프로그램의 성능이 좋은가 ?
4. 사용법과 작동법을 기술하는 설명이 있는가 ?
5. 유지보수가 용이하도록 프로그램이 구성되어 있는가 ?
6. 프로그램을 이해하기 쉬운가 ?

이러한 기준은 소프트웨어, 특히 대형 소프트웨어 시스템을 개발하는데 있어서 매우 중요하다.

동일한 작업을 수행하는 여러 프로그램이 있을 경우에 가능한 한 적은 메모리 공간과 적은 실행 시간을 필요로 하는 프로그램이 바람직할 것이다.

이때 프로그램을 실행하는 시간과 메모리 추정에 초점을 두는 성능 평가를 성능 분석(performance analyis)라고 한다.

일반적으로 프로그램의 성능 분석은 프로그램의 실제 실행 시간을 나타내는 시간 복잡도와 프로그램이 필요로 하는 저장 공간을 나타내는 공간 복잡도를 추정해서 평가한다.

공간 복잡도

프로그램의 공간 복잡도(space complexity)는 프로그램을 실행시켜 완료하는데 필요한 총 저장 공간을 말한다.

일반적으로 어떤 프로그램 P가 필요로 하는 총 저장 공간을 \(S_p\)라 할 때, 이것은 다음과 같이 표현할 수 있다.

\[S_p=S_c+S_e\]

여기서 \(S_c\)와 \(S_e\)는 다음과 같은 고정 공간과 가변 공간을 말한다.

1. 고정 공간 \(S_c\) : 프로그램의 크기나 입출력의 횟수에 관계 없이 고정적으로 필요한 저장 공간을 의미. 이 고정 공간에는 컴파일된 프로그램 명령어 공간(코드 저장을 위한 공간), 단순 변수, 복합 데이터 구조와 변수, 그리고 상수들을 위한 저장 공간이 포함
2. 가변 공간 \(S_e\) : 실행 과정에서 데이터 구조와 변수들이 필요로 하는 저장 공간이 포함. 또한 함수가 순환 호출을 할 때 마다 추가로 필요로 하는 런타임 스택(runtime stack)을 위한 저장 공간도 포함된다. 이 런타임 스택은 함수를 실행하고 제어하는데 필요한 정보를 저장하는 공간을 차례로 보관하는 곳이다.

프로그램의 공간 복잡도를 분석할 때는 보통 가변 공간에 대해 더 중점을 두고 있다.

똑같은 기능을 하는 프로그램 들이 있을 때 많은 공간 복잡도를 가진 것보다 적은 공간 복잡도를 가진 프로그램이 더 성능이 좋고 선호한다고 보아야 한다.

시간 복잡도

프로그램의 시간 복잡도(time complexity)는 프로그램을 실행시켜 완료하는데 걸리는 시간을 의미한다.

일반적으로 어떤 프로그램 \(P\)를 실행하는데 필요한 시간을 \(T_p\)라 할 때, 이것은 다음과 같이 표현할 수 있다.

\[T_p=T_c+T_e\]

여기서 \(T_c\)는 컴파일 시간이고, \(T_e\)는 실행 시간이다.

컴파일 시간은 소스프로그램을 컴파일 하는데 걸리는 시간으로서 프로그램의 실행 특성에 의존하지 않기 때문에 고정적이다.

또한 프로그램이 일단 정확하게 수행된다는 것이 검증되면, 그 프로그램을 재 컴파일하지 않고도 계속해서 반복해 실행시킬 수 있다.

그렇기 때문에 시간 복잡도를 비교할 때는 프로그램의 실제 실행 시간 \(T_e\)만 고려하면 되지만, 프로그램을 실제로 실행시켜보기 전에는 정확한 실행 시간을 계산할 수가 없다.

따라서 이 시간 복잡도에서는 프로그램을 실제로 실행시키지 않고 실행 시간을 추정해 보려는 것이다.

프로그램의 실행 시간을 추정하기 위해서는 두 가지 요소를 알아야 한다.

하나는 단위 명령문 하나를 실행하는데 걸리는 시간이고 또 하나는 실행 빈도수(frequency count)이다.

보통은 프로그램이 실행하는 프로그램 단계(step)의 실행 빈도수로 실행 시간을 계산하면 되기 때문에 단위 명령문의 실제 실행 시간에 대해서는 신경쓸 필요가 없다.

이것은 물론 프로그램의 정확한 실행 시간은 아니지만 프로그램들의 상대적 우열을 비교하는데는 이것으로 충분하다는 데에 기반을 두고 있다.

다시 말해 프로그램을 어떻게 프로그램 단계로 나눌 수 있을 것인지가 핵심이 된다.

프로그램 단계(program step)는 구문, 의미상으로 의미가 있는 계산 단위(compudation unit)로서 실행 시간이 상황에 따라 변하지 않는 것을 말한다.

따라서 시간 복잡도를 위해서는 모든 기본 명령문(지정문, 조건문, 반복문 속의 제어문 그리고 stop, return 등)을 하나의 단위 시간이 걸리는 프로그램 단계로 간주하고, 그에 대한 실행 빈도수만 계산하면 된다.

여기서 유의해야할 것은 프로그램을 프로그램 단계로 계산할 때, 각 프로그램 단계의 실제 실행 시간은 서로 다를 수 있다는 것이다.

예를 들어, \(a=2\)와 같은 간단한 지정문을 하나의 실행 단계로 계산할 때와, \(a=2\cdot b+3\cdot c/d-e+f/g/a/b/c\) 같이 좀 더 복잡한 연산문을 한 단계로 계산할 때 이들의 실제 실행 시간은 서로 다르겠지만 이 시간 복잡도에서는 한 단계로 계산되는 모든 기본 명령문은 실행 시간은 프로그램 단계의 실행 빈도수만 계산하면 된다.

예를 들어 아래 세가지 프로그램 세그먼트를 생각해보자.

a)

x=x+1;

b)

for(i=1;i<=n;i=i+1) do
  x=x+1;

c)

for(i=1;i<=n;i=i+1) do
  for(j=1;j<=n;j=j+1) do
      x=x+1;

프로그램 (a)에서 명령문 x=x+1은 어떤 루프레도 속해 있지 않다고 가정하면, 이 명령문의 실행 빈도수는 1이 될 것이다.

프로그램 (b)에서는 x=x+1이 \(n\)번, 프로그램 (c)에서는 \(n^2\)번 실행될 것이다.

여기서 \(1, n, n^2\)은 \(n\)이 10일 때 각각 1, 10, 100으로 증대되는 차수, 즉 큰 자리수(order of magnitude)를 말해주고 있다.

프로그램 실행에 대한 분석에서는 주로 알고리즘의 이런 차수를 결정하는 데에 중점을 두고 있다.

프로그램의 시간 복잡도 비교에서 순환 프로그램과 반복 프로그램을 비교할 때는 주의를 해야한다.

왜냐하면 순환 프로그램의 단계수는 일반적으로 반복 프로그램의 단계수보다 더 작지만 실행 속도는 반복프로그램보다 순환 프로그램이 더 느린 것이 보통이기 때문이다.

그 이유는 순환 프로그램의 단계가 실행되면서 순환 호출을 할 때 이 호출을 위해 부수적으로 걸리는 시간으로 인해 반복 프로그램의 단계보다 평균적으로 시간이 더 많이 걸리기 때문이다.

시간 복잡도 계산

피보나치 수열의 시간 복잡도를 계산해 보자.

피보나치 수열(Fibonacci sequence)의 각 새로운 항은 두 개의 바로 전항의 합으로 만들어 진다. \(f_0\)를 초항이라 할 때, \(f_0=0, f_1=1\)이고 일반항 \(f_n\)은 다음과 같다.

\[f_n=f_{n-1}+f_{n-2}, n\ge 2\]

아래 프로그램 fib_i()는 음이 아닌 정수 n을 입력으로 받아 \(f_n\)의 값을 반환한다.

fib_i()
    if(n < 0) then stop;
    if(n <= 1) then return n;
    fn2 = 0;
    fn1 = 1;
    for(i = 2; i <= n; i = i++) do {
        fn = fn1 + fn2;
        fn2 = fn1;
        fn1 = fn;
    }
    return fn;
end fib_i()

이 프로그램의 시간 복잡도를 분석하기 위해서는 n < 0, n = 0, n = 1, n > 1의 4가지 경우를 고려하면 된다.

아래 표는 처음 세 가지 경우에 대해 프로그램 단계의 실행 빈도수를 구한 것이다.

실제로 이 세가지 경우는 별로 중요하지 않은데, 이같은 경우는 위의 프로그램을 거의 활용하지 않기 때문이다.

분석에서 가장 중요한 경우는 n>1일 때인데 이 경우는 for 루프로 실제 진입하게 된다.

1, 3행 명령문은 1번 실행되나 2, 4행 명령문은 실행되지 않는다. n\(\ge\)2에 대해 7행 명령문은 n-1번이 아니라 n번 실행된다.

그 이유는 i가 2에서부터 n이 될 때까지 n-1번 실행되며 마지막으로 i가 n+1이 된 후 다시 7행 명령문으로 돌아와 i>n인지를 검사하고 12행 명령문으로 분기하기 때문이다.

따라서 8, 9, 10행 명령문은 n-1번, 7행 명령문은 n번 실행될 것이다.

이것을 요약하면 다음 표와 같다.

시간 복잡도에서 프로그램의 중괄호나 End 명령문은 실행 시간을 0으로 보고 프로그램 단계로 취급하지 않는다.

또한for문의 제어문은 실제로 여러 개의 명령문으로 구성되어 있지만 하나의 단계로 계산한다.

이런 방식으로 프로그램 단계들의 총 실행 빈도수, 즉 프로그램 실행 시간을 계산하면 4n+2(실행하는 문장의 수)가 된다.

이것은 결국 n이 결정되어야 전체 값이 결정되는 것이기 때문에 전체 값의 크기는 n에 의존하게 된다.

이런 의미로 실행 시간 4n+2를 \(O(n)\)으로 표기한다.

이 표기식은 n이 아주 커질 때 4n+2 값의 크기는 n에 달려 있다는 뜻이다.

일반적으로 시간 복잡도를 계산할 때 Big-oh(\(O\)) 표기법을 쓰는데 이 표기법의 정확한 수학적 정의는 다음과 같다.

Big-oh(\(O\))

\(f\)와 \(g\)를 각각 양의 정수를 갖는 함수라 할때, 어떤 두 양의 상수 \(a\)와 \(b\)가 존재하고, 모든 \(n\ge b\)에 대하여, \(f(n)\le a\cdot g(n)\)이면 \(f(n)=O(g(n))\)이다. 즉 함수 \(f(n)\)의 시간복잡도가 \(O(n)\)이라는 뜻이다.

만일 \(f(n)\)이 \(O(g(n))\)의 범위에 들어가면, 우리는 \(f(n)\)의 차수가 \(g(n)\)이라고 말하거나 \(f(n)\)은 \(O(g(n))\)이라고 한다.

이 big-oh 표기법의 기본 아이디어는 만일 \(f(n)\)이 \(O(g(n))\)이라면, \(n\)이 계속적으로 무한히 커질 때 \(f(n)\)의 값은 결국 \(g(n)\)을 상한으로 점점 가깝게 점근적으로 한정되기 때문에, \(g(n)\)을 \(f(n)\)의 어림값으로 볼 수 있다는 것이다.

그런의미로 big-oh(\(O\))를 점근식 표기법(asymptotic notation)이라 한다.

함수 \(f(n)\)은 일반적으로 알고리즘의 연산 시간을 나타내는데 사용된다.

어떤 알고리즘의 연산 시간이 \(O(g(n))\)이라는 것은 실행 시간이 \(g(n)\)의 어떤 상수배 보다는 작다는 뜻이다.

예를들어 앞에서 살펴본 반복식 피보나치 수열 프로그램의 연산 시간은 T(fib_1)=O(n)으로 표시할 수 있다.

Big-oh의 표기법으로 표시되는 연산 시간은 몇 개의 그룹으로 나눌 수 있는데, 이들은 다음과 같은 별도의 이름을 가지고 있다.

\(O(1)\)은 상수 시간(constant time), \(O(\log n)\)은 로그 시간(logarithmic time), \(O(n)\)은 선형 시간(linear time), \(O(n \log n)\)은 n 로그 시간(n logn time), \(O(n^2)\)은 평방 시간(quadratic time), \(O(n^3)\)은 입방 시간(cubic time), \(O(2^n)\)은 지수 시간(exponentail time), \(O(n!)\)은 계승 시간(factorial time)이라 부른다.

또한 k\(\ge\)1에 대해 \(O(n^k)\)로 표현되는 연산 시간을 총칭하여 다항식 시간(polynomial time)이라고도 한다.

만일 어떤 알고리즘의 연산시간이 \(O(\log n)\)이면 n이 아주 클 때 \(O(n)\)보다 훨씬 빠르다.

마찬가지로 \(O(n \log n)\)은 \(O(n^2)\)보다는 좋지만 \(O(n)\)보다는 좋지 않다.

이런 연산 시간의 크기 순서는 다음과 같다.

\[O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\]

프로그램의 실행 시간을 계산하는 목적 중에 하나는 이들의 성능을 서로 비교하기 위한 것이다.

만일 같은 작업을 수행하는데 걸리는 연산시간이 각각 \(O(n)\)과 \(O(n^2)\)인 두 개의 알고리즘이 있다면, 일반적으로 \(O(n)\)인 알고리즘의 성능이 더 나은 것으로 판단한다.

그 이유는 \(n\)이 증가할 때 \(O(n^2)\)의 증가량이 \(O(n)\)의 증가량보다 크기 때문이다.

정리

프로그램 성능(실행 시간)은 실행 환경에 따라 다르기 때문이 이들을 단순 비교하는 것은 불공정하다.

이 실행 환경은 주로 최선의 경우(best case)와 최악의 경우(worst case)로 나눌 수 있다.

최선의 경우는 알고리즘의 시간 복잡도가 가장 작게 되는 경우이고, 최악의 경우는 알고리즘의 복잡도가 가장 크게 되는 경우이다.

따라서 공정한 비교를 위해서는 이 두 경우를 모두 계산해 보아야만 한다.

참고 문서

• 이석호. (2004). 자료 구조와 JAVA. 정익사.