성능 분석과 빅 오(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)

 

---

혹시라도 잘못된 내용이 있다면 덧글로 알려주세요~