성능 분석과 빅 오(Big 'O') 기법을 알아보자
Performance Analysis (성능분석)
Measurement: 측정
성능을 분석하는 것에는 2가지 방법이 있습니다. 첫 번째 방식은 기계 자체에서 직접 실행 시간을 측정하는 것입니다. 그러나 이 방식의 단점이 있습니다. 그것은 사용되는 컴퓨터의 사양에 따라 실행 속도가 달라진다는 것입니다. 때문에 기기의 사양과 관계없이 정량적으로 분석하기 위한 기법을 필요합니다. 이는 아래 [Analysis: 시간과 공간 추정]에서 살펴보겠습니다.
그렇다면 C언어에서 실행 시간을 측정하기 위해서는 어떻게 해야할까요? 아래 글을 참조해 보세요!
2023.10.10 - [Programming Language/Data Structure in C] - C언어에서 코드 실행 시간 측정하는 방법 (Measurement)
Analysis: 시간과 공간 추정
- 특징
- 기계 독립적
- 공간 복잡도
- 시간 복잡도
기계 독립적은 위에서 설명한 것과 마찬가지로 기기의 성능에 관계없이 성능을 추정할 수 있다는 의미입니다.
공간 복잡도는 프로그램이 실행된 이후부터 종료될 때까지 얼마나 많은 공간을 차지하는지를 확인합니다.
시간 복잡도는 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간이며 함수의 호출 횟수, 반복 횟수 등을 확인합니다.
저희는 시간 복잡도를 중점적으로 살펴볼 것입니다. 첫 번째로 실수의 합을 더해 출력하는 함수입니다. 전체 코드는 아래와 같습니다.
배열에서 실수의 합을 반환하는 함수
#include <stdio.h>
float sum(float list[], int n) {
float tempsum;
int i;
tempsum = 0;
for(i = 0; i < n; i++)
tempsum += list[i];
return tempsum;
}
int main( void )
{
float list[] = {0.1, 0.2, 0.3, 0.4, 0.5};
int size = sizeof(list) / sizeof(list[0]);
printf("%1.1f", sum(list, size));
return 0;
}우리가 분석해야 하는 함수는 아래 코드입니다.
float sum(float list[], int n) {
float tempsum;
int i;
tempsum = 0;
for(i = 0; i < n; i++)
tempsum += list[i];
return tempsum;
}함수를 선언하는 부분은 세지 않아도 됩니다. 때문에 선언 부분을 제외하고 계산해보겠습니다.
1: 1
tempsum = 0;2: n
for(i = 0; i < n; i++)
tempsum += list[i];3: 1
return tempsum;계산해보면 총 Step Count는 아래와 같습니다.
Step Count: 1 + n + 1 = n + 2
배열에서 최댓값 찾기
#include <stdio.h>
float arrayMax(float A[], int n) {
float max;
int i;
max = A[0];
for(i = 0; i < n; i++)
if (max < A[i])
max = A[i];
return max;
}
int main( void )
{
float list[] = {0.3, 0.2, 0.5, 0.4, 0.1};
int size = sizeof(list) / sizeof(list[0]);
printf("%1.1f", arrayMax(list, size));
return 0;
}우리가 분석해야 하는 함수는 아래 코드입니다.
float arrayMax(float A[], int n) {
float max;
int i;
max = A[0];
for(i = 0; i < n; i++)
if (max < A[i])
max = A[i];
return max;
}함수를 선언하는 부분은 세지 않아도 됩니다. 때문에 선언 부분을 제외하고 계산해보겠습니다.
1: 1
max = A[0];2: n
for(i = 0; i < n; i++)3: 1
if (max < A[i])4: 1
max = A[i];5: 1
return max;
계산해보면 총 Step Count는 아래와 같습니다.
Step Count: 1 + n + 1 + 1 + 1 = n + 4
행렬 덧셈
#include <stdio.h>
#define M_SIZE 5
void add(float a[][M_SIZE], float b[][M_SIZE], float c[][M_SIZE]) {
int i, j, n = M_SIZE;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
c[i][j] = a[i][j] + b[i][j];
}
int main( void )
{
float list1[][M_SIZE] = {
{0.3, 0.2, 0.5, 0.4, 0.1},
{0.1, 0.2, 0.3, 0.4, 0.5},
{0.5, 0.4, 0.3, 0.2, 0.1},
{0.4, 0.3, 0.2, 0.1, 0.0},
{0.0, 0.1, 0.2, 0.3, 0.4}
};
float list2[][M_SIZE] = {
{0.1, 0.2, 0.3, 0.4, 0.5},
{0.5, 0.4, 0.3, 0.2, 0.1},
{0.4, 0.3, 0.2, 0.1, 0.0},
{0.0, 0.1, 0.2, 0.3, 0.4},
{0.3, 0.2, 0.1, 0.0, 0.1}
};
float result[M_SIZE][M_SIZE];
add(list1, list2, result);
for (int i = 0; i < M_SIZE; i++) {
for (int j = 0; j < M_SIZE; j++) {
printf("%1.1f ", result[i][j]);
}
printf("\n");
}
return 0;
}우리가 분석해야 하는 함수는 아래 코드입니다.
void add(float a[][M_SIZE], float b[][M_SIZE], float c[][M_SIZE]) {
int i, j, n = M_SIZE;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
c[i][j] = a[i][j] + b[i][j];
}함수를 선언하는 부분은 세지 않아도 됩니다. 때문에 선언 부분을 제외하고 계산해보겠습니다.
1: n
for(i = 0; i < n; i++)2: n
for(j = 0; j < n; j++)3: 1
c[i][j] = a[i][j] + b[i][j];계산해보면 총 Step Count는 아래와 같습니다.
Step Count: n * n + 1 = n^2 + 1
이번에는 아래 링크에 있는 구구단 프로그램을 Count 해보겠습니다.
2023.10.10 - [Programming Language/Data Structure in C] - C언어에서 코드 실행 시간 측정하는 방법 (Measurement)
#include <stdio.h>
#define N 9
void main( void )
{
for(int i=1; i<=dan; i++){
for(int j=2; j<=dan; j++){
printf("%d x %d = %d\t", j, i, j*i);
}
printf("\n");
}
}1: n
for(int i=1; i<=N; i++)2: n
for(int j=2; j<=N; j++)3: 1
printf("%d x %d = %d\t", j, i, j*i);4: 1
printf("\n");
계산해보면 총 Step Count는 아래와 같습니다.
Step Count: n * n + 1 + 1 = n^2 + 1 + 1 = 2^2 + 2
그렇다면 시간복잡도가 좋은 프로그램은 어떤 것일까요?
f(x) = 1
h(x) = x
g(x) = x^2
f(x)가 1인 경우는 상수입니다. 이 경우 실행 시간이 일정하기 때문에 시간 복잡도가 가장 좋다고 할 수 있습니다.
h(x)가 x인 경우는 1차 함수입니다. 상수는 무시됩니다. 상수가 영향을 크게 미치지 않기 때문입니다. 상수보다 시간 복잡도는 좋지 않습니다.
g(x)가 x^2인 경우는 2차 함수입니다. 상수와 1차 함수는 무시됩니다. 1차 함수보다 시간 복잡도가 좋지 않습니다.
Big 'oh'
Big 'oh'의 정의는 아래와 같습니다.
f(n) = O(g(n)) if and only if f(n) <= cg(n) for all n >= n_0 (c>0)
아래 함수를 Big 'oh' 형태로 변경하겠습니다.
f(x) = 1
h(x) = x
g(x) = x^2
아래는 Big 'oh' 형태로 변경한 함수입니다.
O(f(x)) = O(1)
O(h(x)) = O(x)
O(g(x)) = O(x^2)
big-O
- f(n) <= cg(n)
- 최대 n만큼 걸림
- n에 대한 m차식에서 같음
big-Ω
- f(n) >= cg(n)
- 최소 n만큼 걸림
- n에 대한 m차식에서 같음
big-θ
- c_1g(n) <= f(n) <= c_2g(1) (Big oh + Omega)
- n에 대한 m차식은 모두 같다
최선, 평균, 최악의 경우
- 최선의 경우(best case)
- 수행시간이 가장 빠른 경우
- 의미 없는 경우가 많음
- 평균의 경우(average case)
- 수행시간이 평균적인 경우
- 계산하기 상당히 까다로움
- 최악의 경우(worst case)
- 수행시간이 가장 늦은 경우
- 가장 널리 사용됨
- 계산하기 쉬우며 경우에 따라 중요할 수 있음
순차탐색 예시
최선의 경우: 찾고자 하는 숫자가 맨 앞에 있는 경우
- O(1)
최악의 경우: 찾고자 하는 숫자가 맨 뒤에 있는 경우
- O(n)
평균적인 경우: 각 요소들이 균일하게 탐색된다고 가정
- (1+2+...+n)/n = (n+1)/2
- O(n)
혹시라도 잘못된 내용이 있다면 덧글로 알려주세요~