2. 시간복잡도와 공간복잡도 (1)

성능 분석과 측정

프로그램의 평가 기준

    - 우리가 원하는 작업을 하는가?

    - 원래 작업의 명세에 부합해서 정확히 작동하는가?

    - 문서화가 되어 있는가?

    - 논리적 작업 단위를 수행하는 기준으로 함수가 생성되었는가?

    - 코드가 읽기 쉬운가?

성능 평가(performance evaluation)

    - 성능 분석(performance analysis) => 사전 예측

    - 성능 측정(performance measurement) => 이후 검사

공간 복잡도

공간복잡도

    - 프로그램을 실행 시켜 완료하는 데 필요한 메모리 양

    - 고정 부분 => 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간

    - 가변 부분 => 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간

    - 프로그램 P의 공간 유고 S(P) = c + Sp (c : 상수, Sp : 인스턴스 특성)

ex 1)

float Abc(float a, float b, float c)
{
    return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
 

  => Sp = 0

ex 2)

inline float Sum(float *a, const int n)
{
   float s = 0;
   for(int i = 0 ; i < n ; i++)
      s+= a[i];
   return s;
}
 

  => Sp(n) = 0

ex 3)

inline float Rsum(float *a, const int n)
{
   if(n<=0) return 0;
   else return(Rsum(a, n-1) + a[n-1]);
}
 

    - Rsum을 호출할 때마다 적어도 네 개의 워드 필요

      (n과 a값, 반환 값, 반환 주소에 필요한 공간 포함)

    - 순환 깊이가 n+1이므로 순환 스택 공간에 4(n+1)

시간 복잡도

시간 복잡도

    - 프로그램을 완전히 실행시키는데 필요한 시간

    - T(P) = 컴파일 시간 + 실행시간 (tp(인스턴스 특성))

    - tP(n) = caADD(n)+csSUB(n)+cmMUL(n)+cdDIV(n) + …

        => n : 인스턴스 특성

        => Ca, Cs, Cm, Cd : +, -, x, / 연산을 위한 상수 시간

             => ADD, SUB, MUL, DIV : 특성 n인 인스턴스에서 각 연산의 실행 횟수

프로그램 단계 수

    - 주석 : 0

    - 선언문 : 0

        => 변수, 상수 정의(int, long, short, char, ... )

        => 사용자 데이터 타입 정의(class, struct, union, template)

        => 접근 결정(private, public, protected, friend)

        => 함수 타입 결정(void, virtual)

    - 산술식 및 지정문 : 1

    - 스위치 명령문

        => switch(<expr>)의 비용 = <expr>의 비용

        => 각 조건의 비용 = 자기의 비용 + 앞서 나온 모든 조건의 비용

    - if~else 문

        => <expr>, <statement1>, <statement2>에 따라 각각 단계수가 할당

    - 함수 호출

        => 값에 의한 전달 인자 포함하지 않을 경우 : 1

        => 값에 인한 전달 인자 포함할 경우 : 값 인자 크기의 합

        => 순환적인 경우 : 호출되는 함수의 지역 변수도 고려

    - 메모리 관리 명령문 : 1(new, delete)

    - 함수 명령문(function statements) : 0

        => 비용이 이미 호출문에 해당

    - 분기 명령문 : 1(continue, break, goto, return)

    

ex1)

float Sum(float *a, const int n)
{
    float s = 0;
    count++;
    for(int i=0;i<n;i++)
    {
        count++;
        s += a[i];
        count++;
    }
    count++;
    count++;
    return s;
}    
 

    => 2n + 3

ex2)

float Rsum(float *a, const int n)
{
    count++;
    if(n <= 0)
    {
        count++;
        return 0;
    }
    else
    {
        count++;
        return (Rsum(a,n-1) + a[n-1]);
    }
}
 

  ==

  => 2n + 2

ex3)

void Add(int **a, int **b, int **c, int m, int n)
{
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            c[i][j] = a[i][j] + b[i][j];
}
 

void Add(int **a, int **b, int **c, int m, int n)
{
    for(int i=0;i<m;i++)
    {
        count++;
        for(int j=0;j<n;j++)
        {
            count++;
            c[i][j] = a[i][j] + b[i][j];
            count++;
        }
        count++;
    }
    count++;
}                                
 

void Add(int **a, int **b, int **c, int m, int n)
{
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            count+=2;
        count+=2;
    }
    count++;
}
 

   => 2mn + 2m + 1

단계 수 테이블

명령문의 실행당 단계 수(s/e : step per execution) 결정

    - s/e : 그 명령문의 실행 결과로 count가 변화하는 양

명령문이 실행되는 총 횟수 계산

float Sum(float * a, const int n)
{
   float s = 0;
   for(int i = 0 ; i < n ; i++)
      s+= a[i];
   return s;
}