검수요청.png검수요청.png

공간복잡도

위키원
이동: 둘러보기, 검색

공간복잡도(Space Complexity)는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다. 계산복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간복잡도(time complexity), 후자를 공간복잡도라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다.[1]

개요

알고리즘은 유한한 횟수의 명령어들을 정해진 순서에 의하여 수행한 다음 언젠가는 반드시 종료되어야 한다. 따라서 알고리즘은 일단 시작된 다음 종료될 때까지의 실행시간이 이치에 맞지 않게 너무 길어서는 안된다. 장기 혹은 바둑과 같은 게임에 대한 알고리즘을 예를 들어 생각해 볼 수 있다. 이와 같은 게임의 알고리즘을 개발할 때, 게임 중 발생할 수 있는 모든 경우를 조사하여 알고리즘을 구성할 수 있다. 그러나 이러한 방법으로는 알고리즘의 개발조차도 불가능할 것이며, 그런 방법에 의한 알고리즘의 실행시 얼마만의 시간 안에 계산을 종료할지도 추측할 수 없게 된다. 따라서 일반적인 알고리즘은 상식적인 시간 안에 실행을 종료할 수 있어야 하며, 가능한 한 빠른 시간내에 실행을 종료할 수 있어야 한다. 이러한 관점에서 알고리즘의 성능을 분석하기 위해 시간복잡도라는 개념을 사용하게 된다. 알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간복잡도 외에 공간복잡도도 있다. 시간복잡도가 알고리즘의 실행시간을 의미한다면 공간복잡도는 알고리즘을 수행시키기 위해 필요한 기억장치(memory)의 크기를 의미한다.[2]

공간복잡도는 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 =으로 표기한다. 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구를 말한다. 즉 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수를 뜻한다. 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간이다. 즉 동적으로 필요한 공간을 말한다..[3]</ref> 알고리즘을 실행시키기 위해 필요한 공간은 다음과 같이 두 가지로 분류해 볼 수 있다.

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

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

계산법

공간복잡도의 계산 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이다.

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

빅오 표기법

빅오 표기법(Big-O notation)이 나타내는 의미는 수학적 정의를 통해 알 수 있다. 빅오 표기법의 수학적 정의는 모든 >에 대하여 º인 양의 상수 가 존재하면 =이다. 예를 들면 은 내가 만든 알고리즘의 시간 효율성(running time)을 의미하고 충분히 큰 값인 과 상수 에 대해

= =

이라고 가정하면

ºº가 성립하는 값이 존재하기 때문에 위의 알고리즘 은 빅오 표기법을 사용하여 로 나타낼 수 있다.[5]

  •  : 상수형 빅-오, 데이터 수에 상관없이 '연산 횟수가 고정'인 유형의 알고리즘을 뜻한다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.
  •  : 로그형 빅-오, '데이터 수의 증가율'에 비하여 '연산횟수의 증가율'이 훨씬 낮은 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.
  •  : 선형 빅-오, 데이터 수와 연산횟수가 비례하는 알고리즘이다.
  •  : 선형 로그형 빅-오, 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가하는 알고리즘이다.
  •  : 지수형 빅-오, '지수적 증가'는 무서운 연산 횟수의 증가를 보이기 때문에 다른 방안을 찾아야 한다.
특징
  • 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다. 예를 들어 와 같이 상수항은 무시하고 표기한다.
  • 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다. 예를 들어 와 같이 영향력이 지배적인 이외에 영향력이 없는 항들은 무시한다.

각주

  1. 계산 복잡도 이론 위키백과 - https://ko.wikipedia.org/wiki/%EA%B3%84%EC%82%B0_%EB%B3%B5%EC%9E%A1%EB%8F%84_%EC%9D%B4%EB%A1%A0
  2. 2.0 2.1 Roopretelcham, 〈복잡도(complexity)의 개념〉, 《티스토리》, 2007-10-24
  3. Kimtaeng, 〈시간복잡도와 공간복잡도(Time Complexity Space Complexity)〉, 《티스토리》, 2018-02-12
  4. 불곰, 〈ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법〉, 《티스토리》, 2018-07-29
  5. 인생의 로그캣, 〈빅오 표기법 (big-O notation) 이란〉, 《티스토리》, 2019-03-04

참고자료

같이 보기


  검수요청.png검수요청.png 이 공간복잡도 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.