시간복잡도와 공간복잡도

알고리즘의 성능분석 방법으로는 '시간복잡도'와 '공간복잡도'를 구해보는 방법이 있습니다.

 

시간복잡도란, 알고리즘이 결과물을 내놓는데까지 필요한 시간입니다. 보통 빅오 표기법을 사용해서 나타내곤 합니다.

예를 들어, C언어로 "Hello World!"를 출력하는 알고리즘의 시간복잡도는 실행할 경우 printf("Hello World!"); 부분이 반드시 한 번 실행될 것입니다. 이 알고리즘의 실행빈도는 1이라고 할 수 있겠습니다.

두 가지 예제에서 실행빈도를 구해보고 그것으로 시간복잡도에 대해서 설명해보겠습니다.

Q. ( 1 ) "Hello World!"를 출력하는 알고리즘의 실행빈도는?

Q. ( 2 ) 숫자를 입력 받고, 입력받은 숫자가 2 초과일 경우, "(입력받은 숫자)는 2 초과입니다."를 입력받은 숫자만큼 출력하는 알고리즘의 실행빈도는?

 

 

A. ( 1 ) "Hello World!"를 다섯 번 출력하고 싶다고 한다면 printf("Hello World!");를 다섯 번 작성해주거나,

printf("Hello World!");
printf("Hello World!"); 
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");

또는 반복문을 사용해서 좀 더 간단하게 반복문을 사용하는 알고리즘을 사용할 수 있습니다.

for(int i = 0; i < 5; i++){
  printf("Hello World!");
}

printf("Hello World!"); 를 직접 다섯 번 작성한 알고리즘의 실행빈도는 5입니다. 반복문을 사용해서 작성한 알고리즘의 실행빈도는 for(int i = 0; i < 5; i++){ 에서 5, printf("Hello World!")에서 5, 총 5 + 5 = 10의 실행빈도를 가집니다. 이처럼 실행빈도가 더 많은 반복문을 사용하는 이유에 대해서는 아래에서 다루겠습니다.

다음으로, 입력받은 변수에 따라 알고리즘의 실행빈도가 어떻게 달라지는지 살펴보겠습니다.

A. ( 2 )

int i;
scanf("%d", &i);
printf("%d", i);
if(i>2){
  for(int j = 0; j < i; j++){
    printf("입력하신 숫자는 2 초과입니다.");
  }
}

입력받은 수( i )가 2일 때, int i; 에서 1, scanf("%d", &i); 에서 1, printf("%d", i);에서 1, if(i>2){ 에서 1, printf("은 2 초과입니다.");} 에서는 0이 되어, 결국 위 알고리즘의 실행빈도는 1 + 1 + 1 + 1 + 0 = 4 가 됩니다.

만약 2보다 큰 n을 입력했을 때 알고리즘의 실행빈도는 어떻게 될까요?

int i; 에서 1, scanf("%d", &i); 에서 1, printf("%d", i); 에서 1, if(i>2){ 에서 1, for(int j = 0; j < i; j++){ 에서 n, printf("은 2 초과입니다.");} 에서 n이 되어, 실행빈도는 총 1 + 1 + 1 + 1 + n + n = 2n + 4 가 됩니다.

 

( 1 ), ( 2 )를 빅오 표기법으로 표현하는 것도 가능합니다.

빅오 표기법에서 실행빈도가 상수인 것, 즉 ( 1 )의 경우 O(1)로 표현되며, 이것은 실행시간이 가장 빠릅니다. ( 2 )의 경우 입력받는 수를 n이라고 하면, n이 2 초과일 경우와 그렇지 않을 경우의 시간복잡도는 달라질 것입니다. n=<2인 경우, 시간복잡도는 O(1)이 될 것이고, n>2인 경우 알고리즘의 시간복잡도는 2n에서 2를 떼고 남은 n으로, O(n)입니다.

빅오 표기법의 O(?)에서 물음표(?)에는 1, n, nlogn, logn 등의 것들이 들어올 수 있습니다. 이 중에서 가장 빠른 시간복잡도는 O(1)입니다.

 

공간복잡도란, 알고리즘이 실행되어 결과를 내놓기까지 필요한 메모리를 말합니다. 이것은 실행할 때마다 다를 수 있는데, 그 이유는 알고리즘이 실행될 때마다 조건문(과 반복문 등)이 실행될수도, 실행되지 않을수도 있기 때문입니다. 참고로 변수 선언부분 같은 곳에서는 메모리가 고정적으로 사용됩니다.