gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. 성능 분석 (실행 가능한 기준)

    - 공간 복잡도 (space complexity) : 필요한 메모리 양

    - 시간 복잡도 (time complexity) : 프로그램 수행 시간

2. 공간 복잡도 

- Fixed space requirements (Sc)

    - 실행 도중에 변하지 않는 것

    - 명령어, 단순 변수, 고정된 구조체 변수, 상수 등

    - 공간 복잡도에 고려하지 않는다.

- Variable space requirement (Sv)

    - 프로그램 실행 중에 요구되는 공간으로 가변적이고 예측이 어렵다.

    - 함수 간 배열 전달, 재귀 호출 등

    - 위험 요소를 내포하고 있으며, 공간 복잡도 평가에서 더욱 중요하다.

- S = (Sc +) Sv

- (ex1)

float abc (float a, float b, float c)
{
    return a + b + b * c + (a + b - c) / (a + b) + 4.00;
}

    -input과 output이 단순 변수로만 이루어져 있고, 명령어도 단순 계산이기 때문에 고정 메모리 공간만 활용하는 코드이다. 

    -Sv(abc) = 0

- (ex2)

float Sum (float list[], int n)
{
    int i;
    float total = 0;
    
    for (i = 0l i < n; i++)
        total = total + list[i];
    
    return total;
}

     - 함수를 호출할 때 배열이 전달되었기 때문에 가변 메모리 공간도 활용한다. 

     - 이 경우 시간 복잡도는 배열 전달 방법에 따라 결정된다.

- (ex3)

float rsum(float list[], int n)
{
    if (n)
        return rsum(list, n-1) + list[n-1];
    else
        return 0;
}

    - 배열이 전달되었고, 재귀 호출이 사용되었기 때문에 가변 메모리 공간을 사용한다.

    - 이 때 rsum함수가 처음을 제외하고 n번 호출되었다.

    - 한 번 호출될 때마다 float list[], int n, rsum(list, n-1) 이 세가지 환경 변수들 (매개 변수 저장공간, 함수 회귀 주소) 이 저장되며, 각각 4bytes의 크기를 갖고 있기 때문에 S = 12n 이다. 

- Call by value 

    - 함수에 배열 "값"을 직접 전달하는 방식이다.

    - 배열 크기에 비례하는 추가적인 메모리 공간이 요구된다.

    - Sv(sum) = n    // n == array size

    - (ex) Pascal

- Call by reference

    - 함수에 배열 "주소"를 전달하는 방식이다.

    - 추가적인 메모리 공간이 필요하지 않다.

    - Sv(sum) = 0

    - (ex) C

3. 시간 복잡도

- Time complexity (T)

    - 알고리즘을 수행하는데 필요한 시간이다. 

    - 컴파일 시간(Tc)과 실행 시간(Te)으로 구성되는데, 컴파일은 완료되고 나면 더이상 수행되지 않으므로 실행 시간을 더 중요시한다.

    - 실행 시간은 컴퓨터 하드웨어 환경에 따라 다르다.

    - 따라서 실제 수행 시간보다는 명령문의 수를 시간 복잡도로 간주하여 사용한다.

- 실행 명령문 표

    - 한 문장에 포함된 명령문의 수 (steps) 를 결정한다.

    - 이 문장이 반복 실행되는 빈도 (frequency) 를 결정한다.

    - (명령문 수) x (빈도)로 이 문장의 총 실행 횟수를 계산한다.

    - 이 때 함수 헤더, 변수 선언, 블록의 시작과 끝은 명령문으로 간주하지 않는다.

    - Σ steps * frequency

- iterative sum 

float sum (float list[], int n) {     // 1
    int i;                            // 2
    float temp = 0;                   // 3
    for (i = 0; i < n; i++)           // 4
        temp += list[i];              // 5
    return temp;                      // 6
}                                     // 7

- recursive sum

float rsum (float list[], int n) {            // 1
    if(n)                                     // 2
        return rsum(lsit, n-1) + list[n-1];   // 3
    return 0;                                 // 4
}                                             // 5

- matrix addition

void add() {                              // 1
    int i, j;                             // 2
    for (i = 0; i < rows; i++)            // 3
        for (j = 0; j < cols; j++)        // 4
            c[i][j] = a[i][j] + b[i][j];  // 5
}                                         // 6

4. 점근적 표기법 

- 입력의 수 n이 매우 커질 때 알고리즘의 복잡도가 증가하는 패턴을 근사적으로 표현하는 것이다. 

- 알고리즘의 성능을 비교하는 데 사용한다.

- n이 매우 증가하는 경우를 가정하여 시간 복잡도의 상한선, 하한선, 상한-하한선의 존재 유무에 따라 O, Ω, θ 등의 기호로 근사적인 복잡도를 표현한다.

- 예를 들어, 두 프로그램의 시간 복잡도가 각각 n² + n, 10n 이라고 가정하자.

  n이 작을 땐 계수에 따라 좌우되겠지만, 결국 n이 커질 경우 다항식의 차수가 더 큰 영향을 미친다.

    - (n <= 9) n² + n <= 10n

    - (n > 9) n² + n > 10n

- 이와 같이 두 개의 시간 복잡도 함수의 실행 명령문의 수가 바뀌는 시점을 분기점이라고 한다. 

- 일반적으로 n이 매우 큰 경우의 수행 성능이 더 중요하다.

4-1. Big Oh O 

- "상한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≦ c·g(n)을 만족하는 양의 상수 c와 n₀가  존재한다면 시잔 복잡도 함수 f(n) = O(g(n))이라고 표기할 수 있다. 이 반대의 경우도 성립한다. 

- f(n) = O(g(n)) 이라고 표기할 수 있다면, 이 알고리즘의 수행 시간이 상한선 c·g(n)을 넘지 않는다는 의미이다.

- (ex1) 

    - f(n) = 10n + 10,000 ∈ O(n)

    - c = 20, n₀ = 1,000 이라고 결정한다면

    - f(n) ≦ 20n for all n ≥ 1,000 인 상황에서 Big Oh를 사용할 수 있다.

- (ex2)

    - f(n) = n³ + n² + n ∈ O(n) 

    - c = 3, n₀ = 1 이라고 결정한다면

    - f(n) ≦ 3n³ for all n ≥ 1 인 상황에서 Big Oh를 사용할 수 있다.

- c는 최고차항의 계수와 f(n)의 항 수로 결정할 수 있다.

- n₀는 그래프를 통해서 결정할 수 있다.

- O(1) 은 n에 관계없이 항상 일정한 명령어 수 k를 갖는다는 의미이다.

4-2. Big Omega Ω

- "하한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≥ c·g(n) 을 만족하는 양의 상수 c와 n₀가 존재한다면, 시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선인 c·g(n) 보다 항상 많이 걸린다. 이 알고리즘의 수행 시간은 최소한 하한선 이상으로 걸린다는 의미이다.

4-3. Big Theta θ

- "상한-하한선"

- n₀ 이상인 모든 n에 대해서 c₁·g(n) ≤ f(n) ≤ c₂·g(n)  을 만족하는 양의 상수 c₁, c₂, n₀가 존재한다면, 시간 복잡도 함수 f(n) = θ(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선 (c₁·g(n))과 상한선 (c₂·g(n)) 사이에 존재한다는 의미이다.

4-4. 시간 복잡도 함수의 종류

- O(1) = constant (Fast)

- O(log n) = logarithm

- O(n) = linear

- O(n log n) = log linear

- O(n²) = quadratic

- O(n³) = cubic

- O(2ⁿ) = exponential

- O(n!) = factorial (Slow)

- O(1) ~ O(n²) : 다루기 쉽기 때문에 n이 클 때 유용하다.

- O(2ⁿ) ~ O(n!) : 다루기 어렵기 때문에 n이 아주 작을 때 유용하다.