시간 복잡도 / 공간 복잡도

1. 시간 복잡도, 공간 복잡도란?

좋은 알고리즘이란 무엇일까?
얻고자 하는 결과를 짧은 시간과 적은 메모리 공간을 이용하여 구해내는 알고리즘을 좋은 알고리즘이라 할 수 있다.
이 때 알고리즘 수행에 드는 시간 효율과 공간 효율을 알아내는 방법이 필요한데, 그것이 시간 복잡도와 공간 복잡도이다.

2. 시간 복잡도

알고리즘의 시간 복잡도를 계산할 때는 알고리즘의 연산의 횟수를 계산하여 정한다.
알고리즘은 경우에 따라 연산 횟수가 최선의 경우, 평균적인 경우, 최악의 경우로 달라질 수 있다.
대체로 최악의 경우를 산정하고 시간 복잡도를 파악한다.
그렇다면 이 때 연산이라고 할 수 있는 것에 무엇이 있을지 알아보자.

1. 대입 연산
2. 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)
3. 비교 연산
4. 함수의 호출

public int sum(int n)
    {
        int temp = 0; // 대입 연산
        for (int i = 0; i < n; i++)
            temp += i; // 사칙 연산
        return temp;
    }

위 코드의 연산의 수를 알아보면, n+1번 연산이 이루어지는 것을 알 수 있다. 그리고 이를 T(n) = n+1 이라고 표현하자. 하지만 알고리즘이 거대하고 복잡해질수록 이처럼 연산의 수를 하나하나 세어볼 수 는 없다. 그렇기에 시간 복잡도를 간단하게 알 수 있는 표기법들이 여러가지 있는데 그 중에서 많이 쓰이는 BIG O 표기법에 대해 알아보자.

2.1. BIG O 표기법

빅오 표기법은 연산 횟수의 함수 T(n)의 최고차항에 O를 씌워서 표기하는 표기법이다.
알기 쉽게 예를 들어서 설명해보겠다.

T(n) = n^3 + n^2 + n + 1 -> O(n^3)
T(n) = 2 x n^2 + 1 -> O(n^2)
T(n) = 5 x n -> O(n)

마치 함수의 극한에서 볼 수 있었던 방식으로, n이 무한대로 커진다고 가정했을 때 최고차항의 차수만 유의미해지기에 가능한 방식이다.

빅오 표기법에서의 순서를 알아보면 아래와 같다. 커질수록 많은 연산 횟수와 시간이 걸린다는 의미이다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

• O(1)
  알고리즘이 한 단계만 거쳐 결과를 얻는다. 데이터와 상관 없이 일정한 실행 속도를 갖는다.

• O(logn)
  - 데이터 양이 늘어나는 것에 비해 시간이 조금 늘어난다.
  - 시간에 비례하여 탐색 가능한 데이터 양이 2^n이 된다.
  - 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 보통 커다란 문제를 일정한 크기의 작은 문제들로 쪼개어 해결하는 과정이다. ex) 이분 탐색

• O(n)
  - 데이터 양에 따라 시간이 정비례하게 늘어난다.
  - for문을 통한 탐색이 대표적인 예이다.

• O(nlogn)
  - 데이터 양이 늘어나는 것보다 조금 더 시간이 늘어난다.
  - 보통 커다란 문제를 작은 문제들로 쪼개어 해결하고 다시 합치는 과정이다. ex) quick sort, merge sort

• O(n^2)
  - 데이터 양에 따라 늘어나는 시간이 데이터 양의 제곱에 비례한다.
  - 이중 루프를 이용한 탐색이 대표적인 예이다.

3. 공간 복잡도

공간 복잡도는 메모리를 얼마나 사용했는지 계산하면 된다.
시간 복잡도와 마찬가지로 최악의 경우를 산정하여 주로 빅오 표기법으로 나타낸다.
예를 들자면 크기가 n인 2차원 배열이 필요하다면 O(n^2)의 공간 복잡도를 갖는다라고 표현할 수 있다.
만약 알고리즘 문제를 위해 공간 복잡도를 알아야한다면 512Mb의 경우는 int 변수를 약 1.2억개 정도 선언할 수 있다는 것을 알고 있으면 편리하다.