시간 복잡도, 공간 복잡도

4. 복잡도(complexity)의 개념

알고리즘의 성능분석에 있어서의 복잡도(complexity)의 개념에 대해 살펴보고 공간복잡도(space complexity)와 시간복잡도(time complexity)에 대해 알아본다.

4.1 알고리즘의 성능분석과 복잡도(complexity)

4.2 공간 복잡도(space complexity)

4.3 시간 복잡도(time complexity)

4.1 알고리즘의 성능분석과 복잡도(complexity)

  앞 장에서도 언급했듯이 알고리즘은 유한한 횟수의 명령어들을 정해진 순서에 의하여 수행한 다음 언젠가는 반드시 종료되어야 한다.(유한성) 따라서 알고리즘은 일단 시작된 다음 종료될 때까지의 실행시간이 이치에 맞지 않게 너무 길어서는 안된다. 장기 혹은 바둑과 같은 게임에 대한 알고리즘을 예를 들어 생각해 볼 수 있다. 이와 같은 게임의 알고리즘을 개발할 때, 게임중 발생할 수 있는 모든 경우를 조사하여 알고리즘을 구성할 수 있다. 그러나 이러한 방법으로는 알고리즘의 개발 조차도 불가능할 것이며, 그런 방법에 의한 알고리즘의 실행시 얼마만의 시간 안에 계산을 종료할 지도 추측할 수 없게 된다.

  따라서, 일반적인 알고리즘은 상식적인 시간 안에 실행을 종료할 수 있어야 하며, 가능한 한 빠른 시간내에 실행을 종료할 수 있어야 한다. 이러한 관점에서 알고리즘의 성능을 분석하기 위해 시간 복잡도(time complexity)라는 개념을 사용하게 된다.

  알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간 복잡도(time complexity) 외에 공간 복잡도(space complexity)도 있다. 시간 복잡도가 알고리즘의 실행시간을 의미한다면 공간 복잡도는 알고리즘을 수행시키기 위해 필요한 기억장치(memory)의 크기를 의미한다.

[정의4.1] 복잡도(complexity)

• 시간 복잡도(time complexity): 알고리즘을 실행하여 종료할때까지 필요한 시간
• 공간 복잡도(space complexity): 알고리즘을 실행하여 종료할때까지 필요한 기억장치의 크기

4.2 공간 복잡도(space complexity)

  주어진 알고리즘을 실행시키기 위해 필요한 기억장치(space)는 다음과 같이 두 가지로 분류해 볼 수 있다.

1. 알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 등이 이에 포함된다.
2. 알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우 순환 스택(recursion stack) 등이 이에 포함된다.

  일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시 필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한다.

  다음은 공간 복잡도를 구하는 예이다.

[예제4.1] 공간 복잡도의 계산 1

float abc(float a, float b, float c)

{

     return(a + b + b*c + (a + b - c)/(a + b) + 4.0);

}

공간 복잡도 = 0

  위의 프로그램에서 공간복잡도를 구하기 위해서 살펴볼 것은 변수 a, b, c 이다. 따라서, float형의 변수가 한 워드(word)를 차지한다고 가정하면, 공간복잡도는 '3워드'라고 생각할 수 있다. 그러나 변수 a, b, c 는 전달되는 인자(parameter)로서 함수 abc내에서 해결하고자 하는 문제와는 무관하다고 볼 수 있으므로 공간 복잡도는 0이다.

[예제4.2] 공간 복잡도 계산 2

float Sum(float a[], int n)

{

     float s = 0.0;

     for(int i = 1; i < = n; i++)

          s += a[i];

     return s;

}

공간 복잡도 = n + 3

  위의 프로그램에서 사용되는 변수는 a[], n, s, i 이다. 이번 예에서도 a[]와 n은 인자로 전달 됨을 볼 수 있다. 그러나 [예제4.1]과는 다르게 변수 a[]는 합을 구하기 위하여 반복문 내에서 n개의 원소가 모두 참조되고 있음을 볼 수 있다. 또한, n은 for-문을 벗어나기 위한 한계값으로 사용된다. 따라서 a[]와 n은 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있다고 볼 수 있다. 그러므로 프로그램의 복잡도는 (a[]를 저장하기 위한 공간) + (변수 n, s, I를 위한 공간) = n + 3 이 된다.

[예제4.3] 공간 복잡도 계산 3

float RSum(float a[], int n)

{

     if(n <= 0)

          return (0.0);

     else

          return (RSum(a, n-1) + a[n]);

}

공간 복잡도 = 3(n + 1)

  위의 프로그램은 순환기법(resursion)으로 작성된 것이다. 위의 경우 살펴볼 변수는 a[], n이다. 우선 변수 n은 if-문 내에서 순환의 한계값으로 사용되고 있음을 볼 수 있다. 또한, 변수 a[]는 합을 구하기 위하여 사용되고 있으며 a[]의 원소 중에서 n번째의 원소만 필요로 한다. 따라서 변수 a[]와 n이 모두 알고리즘과 밀접한 관계가 있으므로, 프로그램이 필요로 하는 공간은 (a[]의 n번째 원소를 의한 공간) + (n을 위한 공간) = 1 + 1 으로 볼 수 있다. 그러나 위의 프로그램은 순환기법에 의해 작성되었음을 고려해야 한다. 즉, 프로그램이 순환적으로 실행될 것을 고려해서 몇번의 순환후에 실행이 종료되는지(the depth of recursion)를 계산해야 하며, 또한 순환을 위해서 필요한 복귀 주소(return address)를 저장할 공간도 계산해야 한다. 그러므로 프로그램의 공간 복잡도는 (depth of recursion)×(a[n], n, 복귀 주소를 위한 공간) = (n+1)×3 이 된다.

4.3 시간 복잡도(time complexity)

  시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을 곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

  이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리즘의 시간 복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간 복잡도를 통해서 이루어진다. 따라서 이번 강좌를 통해서 소개되는 알고리즘들의 분석은 대부분 시간 복잡도를 이용할 것이며 특별한 언급이 없는 한 '복잡도'는 '시간 복잡도'를 의미하게 된다.

  다음은 시간 복잡도를 구하는 예이다.

[예제4.4] 시간 복잡도 계산 1

알고리즘	실행횟수
float Sum(float a[], int n) {      float s = 0.0;      for(int i = 1; i <= n; I++)           s += a[i];      return s; }	- - 1 n + 1 n 1 -

명령어 총 실행횟수 = 2n + 3, 시간 복잡도 = O(n)

  위 알고리즘의 총 실행 횟수는 2n+3 이 되므로 시간 복잡도는 2n+3이다. 또한 복잡도는 일반적으로 'big oh'표기법을 통해서 평균 실행시간을 표현하게 되는데 위의 알고리즘의 경우는 'big oh' 표기법으로 O(n)이 된다. 복잡도의 표기 방법에 대해서는 다음절에서 보다 자세히 살펴보도록 하겠다.

  순환 알고리즘의 경우, 시간 복잡도를 구하기 위하여 명령어의 실행 횟수를 세는 것은 위의 [예제4.4]와 같은 방법으로는 어렵다. 따라서 일반적으로 순환 알고리즘의 시간 복잡도를 구하기 위해서는 순환식(recursive formula)을 이용하게 된다. [예제4.3]에서 소개된 알고리즘을 예로 들면 다음과 같다.

[예제4.5] 시간 복잡도 계산 2

알고리즘	실행횟수
float RSum(float a[], int n) {      if(n <= 0)           return (0.0);      else           return (RSum(a, n-1) + a[n]); }	- - 1 1 - 1 + T(RSum(n-1)) -

명령어 총 실행횟수 = 2n + 1, 시간 복잡도 = O(n)

  위의 알고리즘에서 사용된 순환식을 이용하면 명령어의 실행횟수는 다음과 같음을 알 수 있다.

T(RSum(n)) = 2               ,if n = 0

           = 2 + T(RSum(n-1) ,if n > 0

  이와 같은 순환식은 또한 순환관계(recurrence relation)라고도 말하는데, 이러한 순환관계로부터 총 명령어 실행횟수를 구하는 방법은 다음과 같다.

T(RSum(n)) = 2 + T(RSum(n-1))

           = 2 + ( 2 + T(RSum((n-2)) )

           = 2 + ( 2 + ( 2 + T(RSum((n-3)) ) )

           ......

           = 2×n + T(RSum(0))

           = 2n + 2

 따라서, 명령어 실행횟수의 총 합은 2n+2이고 시간 복잡도는 O(n)이다.

1. 알고리즘의 성능을 측정하기 위한 수단으로서 복잡도(complexity)를 사용하며, 복잡도에는 알고리즘의 수행에 필요한 시간을 의미하는 시간 복잡도(time complexity)와 필요한 기억장치(memory)의 크기를 의미하는 공간 복잡도(space complexity)가 있다.

2. 공간 복잡도는 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있는 부분 즉, 변수를 저장하기 위한 공간, 순환 프로그램일 경우 순환 스택(recursion stack)등을 모두 합한 값으로 나타낸다.

3. 시간 복잡도는 알고리즘을 구성하는 명령어들의 실행횟수를 모두 합한 값으로 나타내며, 일반적인 알고리즘 분석은 시간 복잡도를 통하여 이루어진다.