[개념 학습 및 정리] 시간 복잡도

1. 시간 복잡도

1) 시간 복잡도란 ?

똑같은 문제를 해결해도 빠르고 효율적으로 해결하는 것이 중요하다. 즉, 같은 입력을 제공했을 때, 제한 시간 내에 어느 프로그램이 더 빠른지 프로그램을 돌리지 않아도 예측할 수 있어야 한다.

2) 대략적으로 몇개의 명령을 수행하는가

시간 복잡도	특징
O(1)	입력 데이터 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다. 입력되는 데이터양과 상관없이 일정한 실행 시간을 가지며 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
O(n)	입력 데이터의 크기에 비례해서 처리시간에 걸리는 알고리즘을 표현할 때 사용한다. 데이터양에 따라 시간이 정비례한다.
O(n^2)	데이터 양에 따라 걸리는 시간은 제곱에 비례한다. 효율이 좋지 않기에 권장하지 않는다. 이 유형은 이중 반복문에서 입력 자료를 처리하는 경우에 나타낸다. N값이 큰 값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다. 문제 해결을 위한 단계의 수는 입력값 n의 제곱이다.
O(log n)	데이터양이 많앚도 시간이 조금씩 늘어난다. 시간에 비례하여 탐색 가능한 데이터양이 2의 n승이 된다. 문제를 해결하는데 필요한 단계들ㄹ이 연산마다 특정 요인에 의해 줄어든다. 만약 입력 자료의 수에 따라 실행 시간이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.

대략적으로 몇개의 명령을 수행하는가

다음의 예시에서는 각 줄 단위로 명령어를 수행한다면 대략 O(6)이 걸린다. 하지만 상수 번을 수행하기 때문에 O(1)만큼 수행한다.

int main() {
  int a;
  int b, c;
  
  scanf("%d %d", &b, &c);
  
  a = b + c;
  
  printf("%d\n", a);
  return 0;
}

다음의 예시에서는 O(n+5)을 수행하지만 n이 영향을 많이 미치기 때문에 O(n)만큼 수행한다.

int main() {
  int n;
  int sum = 0;
  
  scanf("%d", &n);
  
  for(int i = 0; j < n; i++) {
    sum += i;
  }
  
  printf("%d\n", sum);
  return 0;
}

다음의 예시는 O(n^2+n)을 수행하지만 n보다 n^2 더 영향을 많이 미치기 때문에 O(n^2)이다.

int main() {
  int n;
  int sum = 0;
  
  scanf("%d", &n);
  
  for(int i = 0; j < n; i++) {
    for(int j = 0; j < n; j++) {
      sum += i*j;
    }
  }
  
  for(int i = 0; j < n; i++) {
    sum += i;
  }
  
  printf("%d\n", sum);
  return 0;
}

다음의 예제는 다음과 같이 시간 복잡도를 찾을 수 있다.

• i가 0 일 때 j는 n개를 수행한다. (0 - n-1)
• i가 0 일 때 j는 n-1개를 수행한다. (1 - n-1)
• i가 0 일 때 j는 n-2개를 수행한다. (2 - n-1)
• i가 n-1일 때는 j는 1개를 수행한다.
• 총 명령 수행 갯수는 n + n-1 + n-2 + ... 1
• (1 + ... + n) = n(n+1)/2

 

즉, O(n(n+1)/2)개를 수행하지만 n^2/2이 더 영향을 미치며, 그 보다 n^2이 더 영향을 미치기 때문에 O(n^2)을 수행한다.

※ 최고차항에 초점을 맞추면 쉽게 알 수 있다.

int main() {
  int n;
  int sum = 0;
  
  scanf("%d", &n);
  
  for(int i = 0; j < n; i++) {
    for(int j = i; j < n; j++) {
      sum += i*j;
    }
  }
  
  printf("%d\n", sum);
  return 0;
}

시간 복잡도는 항상 최악일 때를 생각해야한다. 예를 들어 가장 최선의 경우 1초가 걸리고 최악의 경우 100000초가 걸리는 것보다 최선의 경우 3초가 걸리고 최악의 경우 100초가 걸린 프로그램이 훨씬 좋다는 것을 기본적으로 알 수 있다. 즉, 최선의 경우보다 최악의 경우에 초점을 맞추어야한다.

 

다음과 같은 예제에서는 if문에 안걸릴 경우를 생각해주어야 한다. 따라서 O(n)을 수행한다.

int main() {
  int n;
  int sum = 0;
  
  scanf("%d", &n);
  
  for(int i = 0; j < n; i++) {
    if(i*i == n) {
      printf("%d\n",i);
      break;
    }
  }
  
  printf("%d\n", sum);
  return 0;
}

※ "대략적"에 초점을 맞추었기에 실제 명령 갯수와는 다를 수 있다.

3) 명령 수행 수와 실제 시간의 관계

실제로 명령을 많이 실행하면 오래걸린다. 물론 컴퓨터마다 다르지만, 동일하다는 가정하에 확인하면 다음과 같다.

명령 수행 수과 실제 시간의 관계

 

4) 수행 시간 어림짐작

"대략 1억번의 연산을 수행하면 1초가 걸린다."를 기준으로 정확하지는 않지만 대충 어림짐작할 수 있다.

---

선택 정렬 알고리즘에 대해 대략적인 시간 복잡도를 계산할 경우 다음과 같다.

• 최솟값 찾는데 대략적으로 O(n)
• 최솟값 찾는 행위를 n번 수행
• O(n^2)

 삽입 정렬 알고리즘에 대해 대략적인 시간 복잡도를 계산할 경우 다음과 같다.

• 원소를 삽입시키는데 대략적으로 O(n)
• 삽입을 n번 수행
• O(n^2)

버블 정렬 알고리즘에 대해 대략적인 시간 복잡도를 계산할 경우 다음과 같다.

• 마지막 숫자를 확정하는데 대략적으로 O(n)
• n개의 숫자를 확정
• O(n^2)

5) 자료형별 시간 복잡도

자료형별 시간 복잡도