시간복잡도 & 공간복잡도

 

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도란 시간복잡도와 공간복잡도로 나뉜다.

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 따라서 시간복잡도를 측정함으로써 알고리즘을 위해 필요한 연산의 횟수, 공간복잡를 측정함으로써 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다.

• 시간 복잡도 : 입력 크기에 대해 알고리즘이 얼마나 오래 걸리는지를 의미
• 공간 복잡도 : 입력 크기에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

하지만 효율적인 알고리즘을 사용한다고 했을 때, 보통 시간 복잡도와 공간복잡도는 일종의 거래 관계(trade off)가 성립된다. 메모리를 조금더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 많이 사용하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 있다.

1. 시간 복잡도 (Time Complexity)

시간복잡도를 표현하는 방법에는 오메가 표기법, 세타 표기법, 빅오 표기법이 있다.

오메가 표기법은 최상의 경우, 세타표기법은 평균의 경우, 빅오 표기법은 최악의 경우를 평가한다.

보통 시간복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 일반적으로 코딩테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하기 때문에 빅오 표기법이 많이 쓰인다.

 

빅오 표기법

빅오 표기법 명칭

빅오표기법	명칭
O(1)	상수 시간 (Constant time)
O(logN)	로그 시간 (Log time)
O(N)	선형 시간
O(N logN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

위의 표에서는 위쪽에 있을 수록 빠르다. 여기서 n은 입력 데이터를 의미한다

- O(1)

상수 시간, constant time 이라고 하며, 입력값이 증가해도 시간이 늘어나지 않는다. 즉, 입력값이 아무리 커져도 즉시 출력값을 얻어낼 수 있다. 만약에 인덱스 1의 값을 가져올때 배열의 길이가 5이든 100이든 즉시 출력값을 얻을 수 있다.

e.g. 해시테이블

static void constantTime(int n){
		int[] arr= {1,2,3,4,5};
    System.out.println(arr[1]);
}

- O(log N)

로그 시간, 로그 복잡도 (logarithmic complexity)라고 부르며, 입력 데이터의 크기가 커질수록 처리 시간이 로그(log)만큼 짧아진다. (컴퓨터공학에서 log를 쓰는 경우 밑이 2이므로, 밑을 생략한다. log32= 5, log64 =6 ) 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

e.g. 이진 탐색 트리(Binary Search Tree)

- O(N)

선형 시간, Linear complexity 라고 하며, 입력값이 증가함에 따라 선형적으로 시간 또한 같은 비율로 증가한다.

예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면 이 시간 복잡도를 가진다. 만약 O(2n)이어도 같은 비율로 증가하고 있다면, O(n)이라고 표기한다.

e.g. for문 , 순차탐색

static void Linear(){
    int[] arr= {1,2,3,4,5};
    int sum =0;

    for(int i =0; i< arr.length; i++){
        sum += arr[i];
    }

    System.out.println(sum);
}

- O(N logN)

로그 선형 시간, 알고리즘의 실행 시간이 입력 크기와 입력 크기의 로그 곱에 비례한다. 이런 알고리즘은 입력의 절반(또는 일부)으로 나눌때마다 각 부분을 독립적으로 처리한다.

e.g. 병합정렬, 퀵정렬 ,힙정렬

- O(N^2)

제곱 시간, 입력값이 증가함에 따라 시간이 n의 제곱수에 비례한다. 따라서 n이 커지면 그 시간이 감당할 수 없을 정도로 늘어난다. 만약 입력값이 1일 경우 1초가 걸리는 알고리즘에 5초를 주었더니 25초가 걸린다면, 이 알고리즘의 시간 복잡도는 O(n2)이다.

e.g. 버블 정렬 알고리즘, 삽입 정렬 알고리즘

static void quadraticTime() {
      int[] arr = {1, 2, 3, 4, 5};

      for (int i = 0; i < arr.length; i++) {
          for (int j = 0; j < arr.length; j++) {
              int tmp = j * j;
          }
      }
  }

- O(2^N)

지수 시간, 기하급수적 복잡도라고 부르며, 입력 데이터의 크기에 따라 걸리는 시간의 2의 n 제곱만큼 비례한다. 빅오 표기법 중 가장 느린 시간 복잡도를 가진다.

2. 공간 복잡도 (Space Complexity)

공간복잡도란 알고리즘을 위해 필요한 메모리의 양을 말한다. 공간복잡도를 표기할때도 시간복잡도를 표기했던 것처럼 빅오표기법을 이용한다. 만약 크기가 n인 배열을 입력했는데 , 알고리즘이 내부에서 n * n 의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 N^2가된다.

공간복잡도는 총 공간 = 고정공간 + 가변공간 으로 나타낼 수 있다.

• 고정공간 : 알고리즘 실행에 필요한 고정된 크기의 메모리이다. 예를들면 변수, 상수, 간단한 데이터 구조를 말한다. 밑의 예제에서 a, b, c와 같은 고정 변수를 말한다.

static int space(int a , int b , int c){
    return a + b + c;
}

• 가변공간 : 알고리즘 실행에 따라 크기가 변하는 메모리이다. 예를들면 재귀 스택, 동적 할당된 메모리이다.