공간 복잡도, 시간 복잡도 (작성 중)

우선 공간 복잡도와 시간 복잡도가 왜 필요할까?라는 질문을 던져보자.

공간 복잡도와 시간 복잡도는 프로그램의 퍼포먼스(성능)을 측정할 때 사용되는 개념이다.

그렇다면 프로그램의 퍼포먼스의 성능을 왜 측정하는 것일까. 또한 프로그램이란 무엇인가.

 

프로그램

프로그램은 우리가 원하는 것을 수행하는 하나의 도구이다. 그렇기 때문에 우리가 원하는 것을 제대로 수행할 수 있는 지 검증해야 한다.

우리가 기획했던 설명에 따라서 잘 작동하는 지 확인을 해야하고, 어떻게 사용하는 지와 어떻게 작동하는지를 기술한 설명이 있어야 한다. 

탄탄한 논리적인 하부기능으로 구성된 프로그램이 큰 오류없이 잘 작동할 수 있다. 그래서 코드를 짜기 전에 프로그램의 세부 구조를 잘 짜야한다.

이때 효율적인 동작방식(알고리즘)을 찾아야 프로그램이 더 빨리 실행되고 효율적인 프로그램이 되는 것이다.

 

공간 복잡도

프로그램을 실행하고 완료하는 것에 필요한 메모리의 양이다.

필요한 메모리의 양은 변하지 않는 부분 즉 상수(c)와 변하는 부분(Sp)으로 이루어져 있다.

 

c는 고정 공간이라고 부르며 알고리즘과 무관한 공간이다. 코드 저장 공간, 단순 변수 및 상수이다.

Sp는 가변 공간이라 부르며 알고리즘과 관련이 있는 공간이다. 실행 중 동적으로 필요한 공간이라고 보면 된다.

우리가 기억해야할 것은 Sp이다. 이 Sp는 프로그램의 의존적, 즉 프로그램을 어떻게 짜느냐에 따라서 달라질 수 있는 부분이다. 프로그램에 사용하는 인스턴스의 양이 많아질 수록 공간 복잡도는 커질 것이다.

또한 인스턴스는 프로그램을 통해 물리적인 메모리에 저장된 것 이 인스턴스를 저장하는 것에 필요한 공간의 양이 공간 복잡도라고도 부를 수 있다.

 

n을 데이터의 개수로 가정하면 

3개의 변수가 사용되지만 단순 변수 같은 경우는 포함시키지 않는다. 변하는 공간이 0이기 때문에 공간복잡도는 0이다. 

sum 함수는 리스트와 그 크기를 입력 받고 모든 리스트의 합을 리턴한다. 그리고 단순 변수 s를 선언해 이 공간에다 값을 저장한다. 이 둘은 공간적인 크기는 변하지 않기 때문에 공간 복잡도에 포함시키지 않는다. 그렇기 때문에 공간복잡도는 0이다.

위와 같은 경우는 재귀적인 용법으로 리스트의 모든 수를 더하는 코드이다. 기능적으로 볼 때는 위의 코드와 같다. 

하지만 재귀적인 용법으로 사용했을 때는 데이터의 개수에 따라서 저장되는 공간의 크기가 달라진다. 

이러한 모습으로 코드는 바뀌게 되는데 이 실행공간에 a의 값들이 n의 크기에 따라 나열된다. 그렇기 때문에 이는 Sp에 해당한다.

재귀함수는 n+1번 실행이 된다. 입력 변수 포인터 a와 상수 n, 그리고 그 둘은 또 두가지 값으로 반환되는 공간이 최소한 필요하기 때문에 4(n+1)가 공간복잡도로 볼 수 있다. (근데 다른 자료에서는 공간복잡도를 다르게 계산하는 부분도 있었다.  또한 표기법(빅오 표기법 등)에 따라 다르게 해석할 수 있다..)

 

시간 복잡도

시간 복잡도는 프로그램을 실행할 때 필요한 시간이다. 절대적인 실행 시간은 아니고 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기한다. 여기서 연산의 종류는 산술, 대입, 비교, 이동을 말한다.

연산의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수가 아니라 알고리즘과 입력한 데이터 개수 n에 따라 변한다.

위 코드의 시간복잡도를 계산해보자

명령문의 시행 횟수(s/e)를 각 코드의 실행 횟수와 곱해주면 된다.

위 피보나치 함수의 코드의 시간복잡도를 구해보면 아래와 같다.

시간 복잡도는 n이 0이나 1일 때는 2, 1보다 클 때는 4n+1이다.

빅오 표기법

위의 시간 복잡도 함수를 좀 더 깔끔하고 간편하게 표기하는 방법이 빅오 표기법이다.

빅오 표기법의 수학적 정의에 대해서 알아보자.

두 개의 함수 f(n) 과 g(n) 이 주어졌을 때, 모든 n≥n0 에 대하여 |f(n)|≤c|g(n)| 을 만족하는 2개의 상수 c 와 n0 가 존재하면 f(n)=O(g(n)) 이다.

 

그냥 

다음에 작성할게여;;