공간복잡도

공간복잡도(Space Complexity)는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다.

개요

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

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

계산법

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

참고자료

• Roopretelcham, 〈복잡도(complexity)의 개념〉, 《티스토리》, 2007-10-24
• Kimtaeng, 〈시간복잡도와 공간복잡도(Time Complexity Space Complexity)〉, 《티스토리》, 2018-02-12

같이 보기

• 알고리즘
• 시간복잡도

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

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