시간 복잡도

시간복잡도란 $n$ 개의 입력 데이터에 대하여 알고리즘이 문제를 해결하는 데에 얼만큼의 시간이 걸리는지를 나타내는 것을 말한다. 일반적으로 점근적 표기법(asymptotic notation)을 사용하여 복잡도를 계산한다.

점근적 표기법이란 중요하지 않은 상수와 계수들을 제거하여 알고리즘의 실행시간에서 중요한 성장률에 집중하는 방법을 의미. 즉 가장 큰 영향을 주는 항만 계산하는 것이다.

점근적 표기법은 위와 같이 세 가지 방법이 존재한다. 그러나 시간 복잡도는 최악의 경우에서 해당 알고리즘이 어떤 성능을 낼 지 가늠해보기 위해 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타낸다.

O(1) - 상수 시간

void func (int n) {
  printf("%d\n", n);
}

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)이다.

O(logN) - 로그 시간

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

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)이다.

알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 연산마다 특정 요인에 의해 감소하는 경우에 주로 확인된다.

위 알고리즘은 i 값이 반복할 때마다 2배씩 증가하는데, 반복문이 결국 k번 반복 되었다면 2^k = n. k=logn이므로 시간 복잡도는 O(logN)이 된다.

O(n) - 선형 시간

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

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)이다.

위의 경우 반복문이 n번 수행되므로, 시간 복잡도는 O(n)이다.

O(n^2) - 2차 시간

for(i=0; i < n; i++) {
  for(j=0, j < n; j++) {
    ...
  }
}

입력 크기(n)가 커질 때 연산 횟수가 n^2에 비례해서 증가하면 시간 복잡도는 O(n^2)이다.

위 알고리즘은 for문이 중첩되어 있기 때문에 n^2에 비례해서 연산수가 증가한다. 따라서 시간복잡도는 O(n^2)이다.

O(2^n) - 지수 시간

int func (int n) {
  if (n <= 1) 
    return n;
  return func(n-1) + fun(n-2);
}

한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 2^n 에 비례해서 연산수가 증가한다. 따라서 시간복잡도는 O(2^n)이다.

추가적인 연산 조건으로는 연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타내야 한다.

알고리즘의 성능간 그래프는 다음과 같다.

O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1) 순으로 시간 복잡도가 큰(수행시간이 긴) 알고리즘이다.

n의 값이 커질수록 복잡한 알고리즘은 수행시간이 급격하게 길어지게 되므로, 최대한 시간복잡도를 낮추는 것이 프로그램의 성능을 향상시킬 수 있는 방법이다.

시간복잡도와 함께 알고리즘을 평가하는 지표로 자주 쓰는 것에는 공간 복잡도가 있다.

공간 복잡도는 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 것이다. 이 또한 점근적 표기법(asymptotic notation)을 사용하여 복잡도를 계산한다.

int sum(int a[], int n)
{
  int x = 0;		
  for(int i = 0; i < n; i++) {
    x  = x + a[i];
  }
  return(x);
}

위의 코드는 int arr[n] : 4*n byte (입력 공간) , int n : 4 byte (입력 공간), int x : 4 byte (보조 공간), int i : 4 byte (보조 공간)으로 구성되어 있으므로, 총 4n+12 에 메모리를 요구한다.

메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이 된다.

출처

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

목차 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity) 알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다. 시간 복잡도: 알고리즘의 수행시간을 평가 공간 복잡도: 알고리즘

yoongrammer.tistory.com

haeunlog