[자료구조] 공간복잡도, 시간복잡도, 성능평가

공간복잡도

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

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

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

 

프로그램 P의 공간 요구 S(P) = c + Sₚ

- c: 상수

- Sₚ: 인스턴스 특성

 

예시

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

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

inline float Rsum(float *a, const int n)
{
    if(n<=0) retuen 0;
    else return(Rsum(a,n-1)+a[n-1])
}
/*
*  Rsum을 호출할 떄마다 적어도 4개의 워드 필요
*  n과 a값, 반환 값, 반환 주소에 필요한 공간 포함
*  순환 깊이가 n+1이므로 순환 스택 공간에 4(n+1)
*/

 

시간복잡도

 

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

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

 

tₚ(n) = cₐADD(n) + cₛSUB(n) + cₘMUL(n) + cᵥDIV(n) + ...

• n: 인스턴스 특성
• cₐ, cₛ, cₘ, cᵥ: + - x / 연산을 위한 상수 시간
• ADD, SUB, MUL, DIV: 특성 n인 인스턴스에서 각 연산의 실행 횟수
• 피연산자의 종류, 컴퓨터 성능, 다중 사용자에 의한 다중 프로그램 실행에 따라 시간 복잡도가 달라질 수 있음

 

프로그램 단계 수

코드	단계 수	설명
주석	0	- 주석
선언문	0	- 변수, 상수 정의 - 사용자 데이타 타입 정의 - 접근 결정 - 함수 타입 결정
산술식 및 지정문	1	- 예외: 함수 호출을 포함하는 산술식
반복문	?	- 제어 부분에 대해서만 단계수 고려
스위치 명령문	?	- switch(<sxpr>)의 비용 = <expr>의 비용 - 각 조건의 비용 = 자기의 비용 + 앞서 나온 모든 조건의 비용
if-else 문	?	- <expr>, <statemant1>, <statement2>에 따라 각각 단계수가 할당
함수 호출	1+α	- 값에 의한 전달 인자 포함하지 않을 경우: 1 - 값에 인한 전달 인자 포함할 경우: 각 인자 크기의 합 - 순환적인 경우: 호출되는 함수의 지역 변수도 고려
메모리 관리 명령문	1	- new, delete
함수 명령문	0	- 비용이 이미 호출문에 할당
분기 명령문	1	- continue, break, goto, return

 

예시

float Summ(float *a, const int n)
{
    float s = 0;
    count++; // count는 전역변수
    for (int i = 0; i < n; i++)
    {
        count++; // for의 제어 부분 거칠 때 마다 +1
        s += a[i];
        count++; // 산술문
    }
    count++; // for문 종료할 때 제어 부분 거치고 종료
    count++; // return
    return s;
}

시간복잡도 - 2n+3

 

float Rsum(float *a, const int n)
{
    count++; // if문의 조건식
    if (n <= 0)
    {
        count++; // 리턴
        return 0;
    }
    else
    {
        count++; // 리턴
        return (Rsum(a, n - 1) + a[n - 1]);
    }
}

 

시간복잡도 - 2n+2

 

void Add(int **a, int **b, int **c, int m, int n)
{
    for (int i = 0; i < m; i++)
    {
        count++; // 바깥 for문 제어 부분
        for (int j = 0; j < n; j++)
        {
            count++; // 안쪽 for문의 제어 부분
            c[i][j] = a[i][j] + b[i][j];
            count++; // 산술문
        }
        count++; // for문이 끝날 때 제어 부분 실행하고 끝
    }
    count++; // 바깥 for문이 끝날 때 제어 부분 실행하고 끝
}

시간복잡도 - 2nm+2m+1

 

점근 표기법

O(빅오) - 모든 n, n≥n₀ 에 대해 f(n)≤cg(n)인 조건을 만족시키는 두 양의 상수 c와 n₀가 존재하면 f(n) = O(g(n))

Ω(오메가) - 모든 n, n≥n₀ 에 대해 f(n)≥cg(n)인 조건을 만족시키는 두 양의 상수 c와 n₀가 존재하면 f(n) = Ω(g(n))

Θ(세타) - 모든 n, n≥n₀ 에 대해 c₁g(n)≤f(n)≤c₂g(n)인 조건을 만족시키는 두 양의 상수 c₁, c₂와 n₀가 존재하면 f(n) = Θ(g(n))

 

- 연산 시간

• 상수시간: O(1)
• 로그시간: O(log n)
• 선형시간: O(n)
• n로그시간: O(n log n)
• 평방시간: O(n²)
• 입방시간: O(n³)
• 지수시간: O(2ⁿ)