공간복잡도

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

개요

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

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

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

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

계산법

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

빅오 표기법

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

$f(n)$=$n_{2}+2n+3$ $g(n)$=$n_{2}$

이라고 가정하면

$f(n)$≤$k$º$g(n)$$(n_{2}+2n+3$≤$k$º$n_{2})$가 성립하는 $k$ 값이 존재하기 때문에 위의 알고리즘 $f(n)$은 빅오 표기법을 사용하여 $O(n_{2})$로 나타낼 수 있다.

• $O(1)$  : 상수형 빅-오, 데이터 수에 상관없이 '연산 횟수가 고정'인 유형의 알고리즘을 뜻한다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.
• $O(logn)$  : 로그형 빅-오, '데이터 수의 증가율'에 비하여 '연산횟수의 증가율'이 훨씬 낮은 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.
• $O(n)$  : 선형 빅-오, 데이터 수와 연산횟수가 비례하는 알고리즘이다.
• $O(n*logn)$  : 선형 로그형 빅-오, 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가하는 알고리즘이다.
• $O(2n)$  : 지수형 빅-오, '지수적 증가'는 무서운 연산 횟수의 증가를 보이기 때문에 다른 방안을 찾아야 한다.

특징

• 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다. 예를 들어 $O(2N)$→$O(N)$와 같이 상수항은 무시하고 표기한다.
• 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다. 예를 들어 $O(N_{2}+2N+1)$→$O(N_{2})$와 같이 영향력이 지배적인 $N_{2}$ 이외에 영향력이 없는 항들은 무시한다.

참고자료

• 계산 복잡도 이론 위키백과 - 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
• Roopretelcham, 〈복잡도(complexity)의 개념〉, 《티스토리》, 2007-10-24
• Kimtaeng, 〈시간복잡도와 공간복잡도(Time Complexity Space Complexity)〉, 《티스토리》, 2018-02-12
• 불곰, 〈ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법〉, 《티스토리》, 2018-07-29
• 인생의 로그캣, 〈빅오 표기법 (big-O notation) 이란〉, 《티스토리》, 2019-03-04

같이 보기

• 알고리즘
• 시간복잡도

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

인공지능 : 인공지능 기술 □■⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물 인간적 행위 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 합리적 사고 결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론 강화학습 ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법 인공지능 프로그램 A2I • 어니 • 알파고 • 알파고제로 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌 인공지능 알고리즘 AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 문자인식 ICR • OCR • OMR • 문자인식 인공지능 특징 계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션 계산 복잡도 NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 기술 BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 • 모달 • 모달리티 • 모달창 • 알렉스넷 • 왓슨 • 텔레파시 • 환각 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반