시/공간 복잡도

계산 종류

1. 최선의 경우
   • 빅 오메가 표기법 사용
   • 최소한으로 걸리는 시간을 표기
2. 최악의 경우
   • 빅 오 표기법 사용
   • 최악의 경우 걸리는 시간 표기
   • 일반적으로 가장 많이 사용
3. 평균적인 경우
   • 빅 세타 표기법
   • 알고리즘의 평균 시간을 표기
   • 일반적으로 알고리즘의 평균적인 시간을 구하기 어려워 잘 사용하지 않음

계산법

T(n) = N^2 + 2n + 1 = O(n^2) : 최고차항만 표기.
T(n) = 2n = O(n) : 최고차항 계수 제외.

/* 시간 */
int func (int n) {
    int sum = 0;    // 대입 1
    int i = 0;        // 대입 1

    for (i=0; i<n; i++) {    // 반복 n+1
    sum += 1;                // 덧셈, 대입 2n
    }
    for (i=0; i<n; i++) {    // 반복 n+1
    sum += i;                // 덧셈, 대입 2n
    }

    return sum;                // 리턴 1
}

        > T(n) = 5n + 5 = O(n)

상수시간은 O(1) 로 표기

 /* 공간 */
 int sum(int a[], int n) {    // a[] : int형 4*n byte
 int x = 0;                      // n     : int형 4 byte
 for (int i = 0; i < n; i++) {// i     : int형 4 byte
     x = x + a[i];              // x      : int형 4 byte
 }
 return (x);
 }

         > 4n+12 = O(n)

---