[C++자료구조론] 1. 성능분석과 측정

• 공간 복잡도(space complexity) : 프로그램을 실행시켜 완료하는데 필요한 메모리의 양(RAM관련)
• 고정 부분
• 프로그램의 입출력 특성과 관계 X - 횟수, 크기 등에 상관 X
• 보통 명령어 공간, 단순 변수, 일정 크기의 요소 변수, 상수들을 위한 공간을 포함
• 가변 부분
• 풀려고 하는 문제의 인스턴스에 의해 크기가 결정되는 변수가 필요로 하는 공간과, 참조된 변수가 필요로 하는 공간, 순환 스택 공간으로 구성
• 공간복잡도 S = C(상수) + Sp(인스턴스 특성)
• Sp는 함수가 얼마나 콜되는가에 따라 달라지는 것 같음
• 변수가 여러개 있다고 해서 Sp가 올라가는 것은 아님
• 순환의 깊이에 따라 Sp가 올라갈 수도 내려갈 수도 있음

• 시간 복잡도(time complexity) : 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간(CPU관련)
• 프로그램에 소요되는 시간은 컴파일 시간 + 실행 시간 - SUM(명령어들의 수행시간 * 명령어들이 몇번이나 실행됐는지 센 결과)
• 컴파일 시간은 인스턴스 특성과는 무관하며 컴파일된 프로그램을 재컴파일 하지 않고 여러번 수행된다는 가정 하에 무시 가능 - 프로그램 실행 시간만 고려해도 OK
• 각 단계수(실행 횟수)를 고려하여 시간 복잡도를 계산
• 주석 : 단계수 0
• 선언문 : 변수/상수 정의문, class, struct, union, template, 접근자, 함수 타입 결정문 등은 단계수 0
• 비실행문이거나, 관련 함수가 기동되는 비용에 포함되므로
• 산술식 및 지정문
• 산술식 : +, -, *, / 등은 단계수 1, 다만 함수 호출을 포함하는 산술식은 예외
• 지정문 : = 등은 단계수 1, 다만 인스턴스 특성의 함수를 대입하는 경우 인스턴스 특성과 같은 단계수를 가짐
• 반복문 : 제어 부분만 단계수 고려, 반복문이 실행되는 횟수
• 스위치 명령문 : 수행되는 식의 단계수와 동일, 각 조건의 비용은 자신의 비용 + 앞서 나온 모든 조건의 비용
• if-else문 : 각 수행문에 따라 단계수 할당
• 함수 호출
• 매개변수가 인스턴스 특성에 의존하는 값이 아니라면 단계수 1, 의존하는 값이라면 값 인자의 크기가 단계수, 순환적이라면 지역변수도 고려
• 메모리 관리 명령문 : new, delete, sizeof 등 단계수 1
• new와 delete의 경우 생성자와 소멸자를 묵시적으로 호출할 수 있는데 이때는 함수 호출과 같은 방법으로 계산됨
• 함수 명령문 : 단계수 0
• 분기 명령문 : continue, break, goto, return 등 단계수 1, return 반환값; 일 경우 반환값이 인스턴스 특성의 함수라면 단계수는 반환값과 같음

밑의 예제를 통해 시간 복잡도를 조금 쉽게 이해하며 계산해보기

각 라인당 몇번 실행되는지 구한 후 다 더하면 OK

float Sum(float *a, const int n){

float s = 0;                1

for(int i=0;i<n;i++){        n+1

s += a[i];             n

}

return s;                 1

}

명령어 실행 횟수를 모두 더하면 2n+3

최고로 오래 걸리는 경우(최악의 경우) 시간 복잡도는 Ο(n) - 상수는 모두 제거하고 최고차의 항만 생각함

float Rsum(float a, const int n){

if(n<=0){                        1

return 0;                        1

}

else{

return (Rsum(a, n-1) + a[n-1]);    1 + tRsum(n-1)

}

}

return 값에 순환함수가 들어가 있으므로 명령어 실행횟수는 tRsum(n) = 2 + tRsum(n-1), n>0, tRsum(0) = 2

순환식을 고치면 최종 명령어 실행 횟수가 나오는데 값이 2n+2

최악의 경우 시간 복잡도는 Ο(n)

void Add(int **a, int **b, int **c, int m, int n){

for(int i=0;i<m;i++)                    m+1

for(int j=0;j<n;j++)                m(n+1)

c[i][j] = a[i][j] + b[i][j];    1*mn

}

실행 횟수를 모두 더하면 2mn+2m+1

최악의 경우 시간 복잡도는 Ο(mn)

내가 변화시키고 싶은 특성들을 정해두고 그 특성에 맞춰 시간 복잡도를 계산하는 것이 좋음

• 균형 분기점(break even point) : 시간 복잡도가 큰 A와 작은 B가 있을 때 A가 B보다 빠를 수 있는 조건이 되는 n이 존재함. 그 때의 n이 균형 분기점
• 점근 표기법
• Ο(빅오) : 알고리즘 실행 시간의 상한을 나타냄 - 최악의 경우
• Ω(오메가) : 알고리즘 실행 시간의 하한을 나타냄 - 최고의 경우
• Θ(세타) : 알고리즘 실행 시간의 평균을 나타냄 - 평균의 경우

함수 값
log n	n	n*log n	n^2	n^3	2^n
0	1	0	1	1	2
1	2	2	4	8	4
2	4	8	16	64	16
3	8	24	64	512	256
4	16	64	256	4096	65536
5	32	160	1024	32768	4294967296