0. 프로그램의 성능 평가
1) 프로그램의 일반적인 평가 항목들
- 프로그램이 처음에 정한 문제의 sepcifications을 만족하는가?
- 프로그램의 documentation이 충분한가?
- 프로그램이 readable한가?
- 프로그램이 correct하게 옳은 답을 내는가?
- 문제의 논리적 단위를 생성할 때, 함수를 효율적으로 사용했는가?
- 프로그램의 수행 시간이 늦지 않은가?
- 프로그램이 storage(memory, disk)를 효과적으로 사용하는가?
2) 프로그램의 성능을 측정하는 방법들
(1) Time & Space 측정법(15% 정도)
: Program 성능을 측정하기 위해, Machine(HW)과 독립적인 다음 2가지 SW적 요소를 분석하는 방법
- Time 요소(효율성, efficiency, 속도 지향)
- Space 사용 정도(메모리 공간 점유도, economy, 경제성 지향)
(2) Step Count 법(5% 정도)
: Program(code)의 Step 수를 하나하나 세는 방법
(3) 점근식 표기법(Asymptotic Notation) (거의 대부분, 100% 사용)
: 품질 및 성능 측정, 품질 보증서
1. 모듈1: Time & Space 측정법
1) Program(P)의 Time & Space Complexity
(1) Space & Time을 사용하여 측정하는 이유
- 프로그램 P가 사용하는 1️⃣메모리 공간(Space)과 프로그램의 2️⃣수행 시간(Time)을 측정해서 정량적(수치)으로 보여주는 방법
- 프로그램 P의 정량적 성능을 표현하기 위해 2가지 metric인 1️⃣Space complexity와 2️⃣Time complexity를 사용한다.
(2) 용어 정의 - S(P) & T(P)
- Space complexity: 프로그램 P의 수행 완료에 필요한 memory 용량
S(P): Space Degree of the Program - Time complexity: 프로그램 P의 수행 완료에 필요한 CPU 사용 시간
T(P): Time Efficiency of the Program
2) Space Complexity - S(P)
(1) 고정공간(fixed)과 변이공간(variable)의 합으로 계산됨
- 고정 공간(c): program의 input/output size에 무관한 space(c로 표현함)
1️⃣ Instruction space(실제 프로그램 자체 코드 저장공간)
2️⃣ Space for simple variables(프로그램 내에서 선언된 변수들의 크기를 잰다)
3️⃣ Fixed size structured variable들의 크기(크기를 미리 알 수 있는 struct 등)
4️⃣ Constants들의 크기 - 변이 공간: program이 input/output size에 종속된 space(Sp(I)로 표현). 이 프로그램이 Instance가 됐을 때 space!
* 인스턴스화 = 프로세스가 됨
- 문제 해결 과정(프로그램의 수행 과정 = Run time)에서 instance I에 의하여 결정되는
1️⃣Structured variables의 space와 2️⃣Recursion에 의해 사용된 space의 합으로 구성
- A function of some characteristics of the instance I
3) Time Complexity - T(P)
(1) T(P) 계산법
(2) Run time(execution time) 추정 방법
- 정확한 계산의 단점: 시스템 clock 수로 계산 가능하지만, machine dependent하여 큰 의미가 없다.
- 실용적인 대안: program이 수행하는 operation의 수로 추정하며, machine independent하게 추정하면 된다.
(-> 다음 모듈에서 배울, Program Step을 이용하자!)
[ 모듈 정리 ] Time & Space 측정법
2. 모듈2: Step Count법
1) Program Step을 세는 방법
- 정의: Syntactically 혹은 semantically 의미 있는 program의 segment(code 자체)이다. 이것은 running time이 instance characteristics와 무관한 특징을 가진다.
- 선언은 관심 없음. assignment만!
- 프로그램 Step Count법 예제 #1: count
float sum(float list [], int n)
{
int count = 0; // for counting steps, count 변수 선언
//시작
float tempsum = 0;
count++;
int i; // declaration은 무시
for(i = 0; i < n; i++){
count++; // for 반복문 때문. 반복문 실행될 때마다 count ++;
tempsum += list[i];
count++;
}
count++; // for 반복문 빠져나올 때 조건 검사했으므로 마지막 execution of for. count.
count++; // return으로 함수 끝나기 전에 미리 count
return tempsum;
}
- 프로그램 Step Count법 예제 #2: Recursive summing
float rsum(float list [], int n)
{
count ++; // 아래 줄의 if 때문에 count++;
if (n) {
count++; // 아래의 return rsum 때문에 count++;
return rsum(list, n-1) + list[n-1];
}
count++; // 아래의 return 때문에 count++;
return 0;
}
- 프로그램 Step Count법 예제#3
void add(int a[][MAX_SIZE],
int b[][MAX_SIZE],
int c[][MAX_SIZE],
int rows, int cols)
{
int i, j, count // 선언은 무시
for(i=0; i < rows; i++){
count++; // 반복문 들어올 때마다
for(j=0; j < cols; j++){
count++; // 반복문 들어올 때마다
c[i][j] = a[i][j] + n[i][j];
count++; // 위의 코드 때문에
}
count++; // 반복문 나올때
}
count++; // 반복문 나올 때
}* for 반복문에서 step count는 for 반복문 들어가자마자와 나오자마자 센다.
[ 모듈 정리 ] 프로그램 Step Count법과 그 문제점
- Program의 step을 count하는 목적은
1️⃣ 서로 다른 두 program들의 time complexity를 상대적으로 분석하고 비교
2️⃣ Instance(n)의 characteristic들(움직임, 루프 등)이 변할 때, run time의 증가치 분석 - 문제점
1️⃣ (1)과 (2)가 분명히 연산양이 다름에도, 동등하게 1 step으로 count된다는 것은 불공정하다.
2️⃣ 프로그램이 큰 경우, 정확한 step count는 일반적으로 어렵다.
3️⃣ 모든 문장에 count++ 문장을 넣는 것은 쉽지 않다.
✅ 해결방안: program의 time과 space complexity를 잘 나타내는 개념이 필요하다.
3. 모듈3: 점근식 표기법(Asymptotic Notation) - 분석적 방법
1) Asymptotic Notation 개요
(1) 정의: Upper bound complexity, Big-O, "빅오"라고 읽음
- 해설
g(n)은 f(n)을 포함할 정도로 크게 설정한 후, f(n)은 g(n)보다 작다고 말한다.
f(n)은 항상 g(n)보다 작으므로, f(n)이 자신을 소개할 때,
"난 g(n)보다 작다. g(n)은 나의 Upper Bound다."라고 말할 수 있다.
(2) 예시
- 3n + 2 <= O(4n)
- 10n^2 + 4n + 2 <= O(10n^4)
2) Upper Bound Complexity(O)
(1) f(n) = O(g(n))
- "g(n)이 f(n)의 Upper Bound다"라고 읽는다.
- 의미: 이것은 "f(n) 함수의 결과치가 g(n) 함수의 것보다 클 수 없다" -> f(n)이 아무리 클지라도, g(n)보다는 작다.
(2) g(n) 설정법: f(n)보다는 크지만, 가능한 f(n)에 근접한 작은 값으로 잡아야, f(n)을 잘 설명할 수 있게 된다.
-> g(n) 설정 시, f(n)에 가깝게 설정할수록, f(n)이 더 잘 설명된다.
(3) Big-O 예시
3) Lower Bound Complexity(Ω) - 트리 검색엔진의 기반
(1) f(n) = Ω(g(n))
- "g(n)이 f(n)의 Lower Bound다"라고 읽는다.
- 의미: 이것은 "f(n) 함수의 결과치가 g(n) 함수의 것보다 작을 수 없다." -> f(n)이 아무리 작아도, g(n)보다는 크다.
(2) Big-Omega(Ω) 설정법
: f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a,b가 존재하고(주어지고)
모든 n>=b에 대해 f(n)>=a·g(n)이면, f(n) = Ω(g(n))
(3) Big-Ω 예시
4) Both Bound Complexity( θ )
(1) f(n) = θ(g(n))
- 의미: g(n)이 f(n)보다 작기도 하고 크기도 한 것이다.(f(n)에서 가장 큰 부분?... 인가?...)
(2) Big-Theta(θ) 설정법
: f, g가 양의 정수를 갖는 함수일 때, 세 양의 상수 a,b,c가 존재하고(주어지고),
모든 n >= c에 대해, a·g(n) <= f(n) <= b·g(n)이면, f(n) = θ(g(n))
(3) Big-Theta(θ) 예
5) 점근적 표기법 예제
6) 점근적 표기법의 상대적 성능 비교 분석
- 최악의 경우를 해당 프로그램의 성능으로 판단함
- 모듈1에서 배운 Time Complexity라는 용어는, 이제 Big-O로 표현되는 점근적 복잡도가 더 많이 사용되면서 Time Complexity라 하면 Big-O 표현이 대표됨. 현재는 점근적 복잡도가 P의 성능을 나타내는 Time complexity의 대명사로 사용됨.
- 우선순위
[ 모듈 정리 ]
