[자료구조] by c언어 #02 시간복잡도, 공간복잡도, Big-O 표기법

공간 복잡도(Space Complexity) : 알고리즘에 사용되는 메모리 총량 

 

시간 복잡도(Time Complexity) : 알고리즘에 수행되는 연산 횟수 총량

 

 

예시들을 통해 공간복잡도에 대해 알아보겠다.

---

ㅡㅡㅡㅡㅡ

int get_sum(int arr[], int n) {

   int sum = 0;

   int i = 0;

   for (i = 0; i < n; ++i) {

        sum += arr[i];

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

공간복잡도 = n + 3 

 

3은 sum, i, n 이 세 개의 변수를 의미한다.

---

ㅡㅡㅡㅡㅡ

int get_sum(int** arr, int a, int b) {

   int sum = 0;

   int i = 0, j = 0;

   for (i = 0; i < a; ++i) {

        for(j = 0; j < b; ++j){

            sum += arr[i][j];

        }

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

공간복잡도 = a * b + 5

 

5: sum, a, b, i, j

---

예시들을 통해 시간복잡도에 대해 알아보겠다.

ㅡㅡㅡㅡㅡ

int get_sum(int arr[], int n) {

   int sum = 0;

   int i = 0;

   for (i = 0; i < n; ++i) {

        sum += arr[i];

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도: n

 

위 for문을 n회 반복한다.

---

ㅡㅡㅡㅡㅡ

int get_sum(int arr[], int n) {

   int sum = 0;

   int i = 0;

   for (i = 0; i < n; i+=2) {

        sum += arr[i];

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = n/2

---

ㅡㅡㅡㅡㅡ

int get_sum(int** arr, int a, int b) {

   int sum = 0;

   int i = 0, j = 0;

   for (i = 0; i < a; ++i) {

        for(j = 0; j < b; ++j){

            sum += arr[i][j];

        }

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

공간복잡도 = a * b

---

ㅡㅡㅡㅡㅡ

int get_sum(int n) {

   int sum = 0;

   int i;

   for (i = 0; i < n; ++i) {

        sum += i;

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = n

---

ㅡㅡㅡㅡㅡ

int get_sum(int** arr, int n) {

   int sum = 0;

   int i = 0, j = 0;

   for (i = 0; i < n; ++i) {

        for(j = 0; j < n; ++j){

            sum += arr[i][j];

        }

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = n**2    (n의 2승)

---

ㅡㅡㅡㅡㅡ

int get_sum(int n) {

   int sum = 0;

   int i;

   for (i = 1; i <= n; i*=2) {

        sum += i;

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = log2(n)

밑이 2인 로그에 n

--> 대략 log2(n) 꼴 이다.

 

**그래프가 가파를수록 (기울기가 클수록) 실용성이 감소한다.**

 

 

---

ㅡㅡㅡㅡㅡ

int get_sum(int n) {

   int sum = 0;

   int i, j;

   for (i = 1; i <= n; ++i) {

        for(j = 1; j <= i; ++j){

            sum += j;

        }

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = n ( n + 1 ) / 2

ㅡㅡㅡㅡㅡ

n=5 인 경우.

---

ㅡㅡㅡㅡㅡ

int get_sum(int n) {

   int sum = 0;

   int i, j;

   for (i = 1; i <= n; ++i) {      // n회 반복.

        for(j = 1; j <= i; i*=2){       // log2(n).       --> n*log2(n)

            sum += j;     

        }

   }

   return sum;

}

ㅡㅡㅡㅡㅡ

시간복잡도 = n log2(n)

 

---

빅-오 표기법(Big-O Notation)

시간복잡도와 공간복잡도의 최고차항만을 표기하여

간략하게 나타내는 표기법

보통 알고리즘을 수행하는 데 걸리는 표준 시간 대신 최악의 시간을 산출하여 표기함

 

예)

 

  T(n) = 3n + 1     -> O(n)

  T(n) = n**2 + 3n + 1     ->  O(n2)

  T(n) = 26n**3+ n + 255   ->  O(n3)

 

 

 

표기	이름	1	2	4	8	16	32
O(1)	상수형(Constant)	1	1	1	1	1	1
O(n)	선형(Linear)	1	2	4	8	16	32
O(log n)	로그형(Logarithmic)	0	1	2	3	4	5
O(n log n)	선형 로그형(Log Linear)	0	2	8	24	64	160
O(n2)	평방형(Quadratic)	1	4	16	64	256	1024
O(n3)	입방형(Cubic)	1	8	64	512	4,096‬	32,768
O(2n)	지수형(Exponential)	2	4	16	256	65,536‬	4,294,967,296‬
O(n!)	계승형(Factorial)	1	2	24	40,320‬	20,922,789,888,000‬	2.6313083693369353016721801216e+35‬

---

O(1)의 예 (반복이 되지 않는 알고리즘)

void test1() {

  printf("Hello!");

}

void test2(int arr[]) {

  printf("%d", arr[2]);

}

void test3(int n) {

  if (n % 2)

      printf("홀수");

  else

      printf("짝수");

}

---

O(n)의 예 (선형 구조의 순차 탐색)

void test(int arr[], int n) {

   int i;

   for (i = 0; i < n; ++i)

      printf("%d", arr[i]);

}

---

O(log n)의 예 (이진 탐색)

int index(int arr[], int n, int target) {

   int i = n / 2;  // i는 2로 나눈 몫.

   while (i >= -1 && i < n) { 

           if (target == arr[i])

              return i;

           if (target > arr[i]) {

              i = (n - i) / 2 + i;

              continue;

           }

           if (target < arr[i])

                i = i / 2; 

   } 

   return -1;

}

---

O(n log n)의 예 (Quick Sort, Heap Sort)

 

O(n2)의 예 (이중 반복문의 처리)

O(n3)의 예 (삼중 반복문의 처리)