우리가 사용하는 만드는 프로그램은 알게 모르게 성능 분석을 항상 받게 된다.
로딩 시간이 길어지면 사용자가 느끼기게 프로그램에 문제가 생겼다던가 혹은 무언가 잘못되었다고 판단할 가능성이 높아진다. 일반적인 홈페이지를 사용했을 때 3초 이상의 로딩 시간이 생기게 되면 F5를 눌러 새로고침을 실행할 확률이 높아진다. 물론 이러한 이유 말고도 다양한 이유가 있지만, 바로 느껴지는 예로는 인터넷 사용 예가 있다.
그래서 특정 프로그램을 판단할 때는 성능 분석하기 위한 여러가지 도구가 존재한다. 그 중 하나가 정수론과 해석학에서 사용되는 점근 표기법(asymptotic notation)을 사용하게 된다.
점근 표기법(asymptotic notation)은 조금 있다가 이야기하도록 하고, 기본적인 성능 분석에 사용되는 방법에 대해 살펴보도록 하자.
#목차
3. 점근 표기법(asymptotic notation)
소프트웨어를 실행한다고 하면, 윈도우 환경에서 우리는 특정 프로그램을 "다운로드"받아서 "실행"하고 기다린다.
그렇다면 다운로드 받고 실행하고 기다리는 행위에서 우리는 2가지를 기대할 수 있다.
다운로드 받는 상황에서, 용량에 대한 생각할 수 있고
실행하고 기다리는 상황에서, 기다림의 시간에 대해 생각할 수 있다.
효율을 좋아하는 사람으로써 이 두가지를 신경 안 쓸 수 없다.
그래서 알고리즘에서도 두 가지 측면에서 분석을 하게 된다.
· 공간복잡도 (space complexity)
· 시간복잡도 (time complexity)
말은 거창하지만, 결국에 이야기하는 것은 얼마만큼의 용량을 잡아먹으면서, 얼마만큼의 시간이 걸리는가?
이것이 질문인 것이다.
혹은 공간복잡도는 메모리 공간의 총량, 시간복잡도는 계산 횟수의 총량로 본다.
시간복잡도에서 계산 횟수의 총량으로 보는 이유는 컴퓨터의 연산 속도에 따라서 다른 값이 나오기 때문에 일정한 측정 결과를 얻을 수 없기 때문에 보편적으로 사용할 수 있는 값을 얻기 위해서 계산한 횟수를 사용하는 것이다.
(단적인 예로, 팬티엄 CPU와 요새 나오는 i9급 cpu로 계산하면 1개 연산을 실행하는데 실행 시간의 차이로 인해 동일한 결과를 얻지 못하므로 연산 횟수를 측정함으로써 다른 계산 성능을 지녀도 비교가 가능하게 만들기 위한 것이다.)
(다른 예시로는 일반 컴퓨터로는 10초 걸리던 특정 알고리즘이 슈퍼컴퓨터로 실행하니 0.0001초 만에 끝났다고 해서 알고리즘이 효율화가 이뤄진 것은 아닌 것이기 때문이다.)
공간복잡도 (space complexity)
공간복잡도는 두 가지 요소가 존재한다.
1. 고정 공간 요구 (Fixed space requirements)
프로그램 입출력과 관련없이 항상 할당하는 공간을 의미한다. 기본적으로 고정 공간 할당은 코드 저장을 위한 공간이나, 단순한 변수(가령 예를 들면, for문에서 쓰이는 i와 같은 변수들), 구조체에 해당하는 변수, 그리고 상수가 이러한 고정 공간에 해당한다.
2. 가변 공간 요구 (Variable space requirements)
가변 공간 요구의 경우, 특정 함수의 호출이 있거나, 인스턴스를 만들어 졌을 경우에 생성되는 공간을 의미한다. 예를 들어 순환 호출을 하게 될 경우에 추가 되는 공간을 포함하게 된다. 이는 얼마만큼 순환하느냐에 따라 값이 결정되기에 가변 공간 요구라 한다.
일반적으로 프로그램에서 관심사는 고정 공간 요구보다도 가변 공간 요구에 집중해서 프로그램을 개발하게 된다.
(입력된 변수에 따라 공간의 크기가 결정되기에 많은 입력이 있는 프로그램이라면 가변 공간을 주의해서 개발해야 한다. 요새는 빅데이터의 경우 많은 입력이 들어오기 때문에 가변 공간을 생각하며 만들어야 한다.
하지만 일반적인 프로그램이라면 늘어난 저장 공간으로 인해 고정 공간 요구는 어느정도 무시된다.
임베디드 소프트웨어의 경우라면 고정 공간 요구 또한 조심해야 하지만, 일반적으로 그렇진 않다.)
\[S(P) = c + S_{p}(I)\]
c는 고정 공간 요구 \[S_{p}(I)는 가변 공간 요구\]
I는 생성된 인스턴스이다.
인스턴스에서는 다양한 변수가 존재하는데, 입력과 출력의 횟수, 크기, 반복함수 등 다양한 값이 존재한다.
입력이 3n을 갖는 배열이면 이 인스턴스는 3n이 인스턴스의 특성이 되는 것이다.
간단한 코드를 통해 살펴보도록 하자.
int add(int number1, int number2)
{
return number1 + number2;
}2개의 변수를 매개변수로 받아서 합을 리턴하는 add함수가 있다고 가정하자. 그렇다면 이 코드는 고정 공간만을 갖고 있는 것이다. 2개의 입력을 받았으며, 1개의 출력을 보내고 있다.
number1, number2의 2개의 정수의 매개변수를 사용하고 있으므로 1워드 + 1워드 = 2워드
총 2워드의 고정 공간을 갖는다. (64비트 운영체제에서는 1워드는 8바이트의 고정 공간을 갖는다. )
그리고 여기의 가변 공간 요구는 \[S_{add}(n) = 0\]이다. (고정값 외에는 없기 때문에 가변 공간 요구는 0이다.)
공간복잡도는 \[S(P) = 16 + 0 = 16\]가 되는 것이다.
코드 하나를 더 보도록 하자.
int sum(int num_list[], int n)
{
int sum = 0;
int i;
for( i = 0 ; i < n ; i++){
sum += num_list[i];
}
return sum;
}다음의 코드는 sum으로 함수가 정의되어 있다.
이 코드는 num_list[]가 정의되어 있으므로 n개 만큼을 전달받는다고 생각할지도 모른다. 하지만 주의해야 한다.
Pascal의 경우 배열 전체를 복사해서 전달받을 수도 있다. 그렇다면 n의 공간복잡도를 갖는다. 하지만 C언어 등 배열의 주소를 전달받는 경우에는 배열을 복사하지 않는다. (C언어를 기준으로 배열의 첫번째 값의 주소를 전달받는다.)
그러므로 \[S_{sum}(n) = 0\] 가 된다. [가변 공간 요구임을 주의하자]
고정 공간은 선언된 변수를 기반으로 생각하면 된다. (배열의 주소를 받는 num_list[] : 1워드, int n : 1워드, int sum : 1워드, int i : 1워드에 해당한다. 총 고정 공간 할당량은 4워드가 된다. 4 * 16 = 64바이트가 된다.)
그렇다면 가변 공간에 대해서는 어떻게 봐야 하는가?
재귀적(recursively)으로 정의된 함수에 대해서 생각해보도록 하자.
int anyFunction(int list[], int n)
{
if( n != 0){
return anyFunction(list, n-1);
}
return 0;
}배열 list[]의 주소와 int n에 해당하는 변수를 전달받는다. return 받는 복귀 주소를 위한 주소가 필요하다.
각각 1개의 배열의 주소값을 저장할 공간과 복귀 주소를 저장할 공간 그리고 정수 변수값 1개를 저장할 공간이 필요하다. 총 3워드가 필요하다. 1번 호출될 때 필요한 공간은 3워드가 필요하므로 64비트 운영체제 기준으로 8바이트 * 3 = 24바이트가 공간 할당이 일어난다.
n의 값이 10이라면 10번의 할당이 일어나므로 10 * 24 = 240바이트의 공간이 필요하다.
이를 재귀함수 대신에 반복함수(for, while)등을 써서 표현한다면 가변 공간은 없어지고 고정 공간만 남게 되는 것이다.
(단, 재귀함수의 가장 큰 장점은 문제를 단순하게 만들어준다는 데 의의가 있으므로 재귀함수가 무조건 나쁜것은 아니다.)
※ 재귀 함수는 반복 함수보다 더 많은 오버헤드를 포함하고 있다.
시간복잡도 (time complexity)
점근 표기법(asymptotic notation)