복잡도(Complexity)란

알고리즘의 성능을 나타내는 척도로,
시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.

1. 시간 복잡도

시간 복잡도(Time Complexity)는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

다음의 c++로 작성된 두 예제 코드를 살펴보자. 두 예제는 모두 아래와 같은 벡터를 입력으로 받는다.

vector<int> arr = {1,2,3,4,5,6,7,8,9,10};

ex1) 정수 배열의 각 원소를 모두 더하여 반환하는 함수

int sum(vector<int> arr){
    int ans = 0;
    for (int i : arr){ ans += i; }
    return ans;
}

ex2) 정수 배열을 순회하며 각 원소까지 포함하여 이전 원소들을 모두 더한 값을 반환하는 함수

int sum2(vector<int> arr){
    int ans = 0;
    for (int i = 0; i < arr.size(); i++){
        for (int j = 0; j <= i; j++){
            ans += arr[j];
        }
    }
    return ans;
}

1번째 예제는 for문을 통해 arr의 각 원소를 순회하고,
2번째 예제는 이중for문을 사용하여 arr의 각 원소를 순회한다.

이때 arr 벡터의 원소의 개수를 n이라 하면

• ex1 -> O(N)
• ex2 -> O(N^2)
  의 시간복잡도를 가진다고 할 수 있다. 이때 O(??)로 나타낸 것을 “빅오 표기법(big-O notation)”이라 하며,
  빅오 표기법은 시간 복잡도를 표현하는 방법으로 자세한 내용은 차후 빅오 표기법 관련 게시글에서 다루도록 하겠다.
  
  

각설,
위 두 예제 ex1과 ex2를 비교하였을 때 연산의 횟수가 더 큰 ex2가 시간복잡도가 안 좋다, 즉 더 오랜 시간이 걸린다는 것이다.

2. 공간 복잡도

공간 복잡도(Space Complexity)는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

다음의 c++로 작성된 두 예제 코드를 살펴보자

ex3) 재귀함수를 이용한 팩토리얼 구하기

int factorial(int n){
    if ((n == 1) || n == 0){
        return 1;
    }
    return n*factorial(n-1);
}

ex4) 반복문을 이용한 팩토리얼 구하기

int factorial2(int n){
    int i = 0;
    int result = 1;
    for (int i = 1; i <= n; i++){
        result *= i;
    }
    return result;
}

위 두 예제의 기능은 모두 양의 정수 n이 주어졌을 때, n!을 계산한다. 기능상으론 동일하나

공간 복잡도의 관점에서 보았을때, ex3는 함수가 재귀호출 될 때마다 새로운 변수 n이 메모리 공간을 차지하고
ex4는 result 변수의 값을 변경하여 계산하기에, n이 커질 수록 ex3보다 훨씬 적은 메모리 공간을 차지한다.

따라서,
ex4의 공간 복잡도가 ex3의 공간 복잡도보다 좋다, 즉 메모리 공간을 덜 차지한다는 것을 알 수 있다.

공간 복잡도 역시 앞서 잠깐 언급했던, 빅오 표기법으로 표현 가능하며 이후 다룰 빅오 표기법 게시글에서 자세히 알아보겠다.

• 사실 시간 복잡도와 공간 복잡도를 비교할 때 같은 목적을 가지는 두 알고리즘을 비교하는 것이 옳으나,
  위 시간 복잡도 관련 예제는 단순 개념의 파악을 위해서 다른 목적의 알고리즘을 예시로 들었다.