시간복잡도, 공간복잡도

1.   복잡도(Complexity)

복잡도란 알고리즘의 성능을 나타내는 지표이다.

복잡도는 가독성(Readability)와 다른 의미로 쓰인다. 즉, 코드가 얼마나 복잡하고 알아보기 어려운지를 의미하는 것이 아니라, 불특정한 함수의 성능적인 측면에서의 복잡도를 의미한다.

1. 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
2. 공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

이때, 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도 가 낮은 알고리즘이 좋은 알고리즘이다.

 

2.  시간 복잡도(Time Complexity)

시간 복잡도란 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간을 의미한다.

같은 결과를 가져오는 코드라면 시간 복잡도가 작은수록 더 효율적인 알고리즘인 것이다.

시간 복잡도는 여러가지 개념이 있지만 그중 'worst case' 를 기준으로 표기하는 빅-오(Big-O) 표기법을 사용한다.

즉, 아무리 오래 걸려도 이것보단 오래걸리지 않는 시간을 기준으로 알고리즘의 성능을 표기하는 것이다.

 

시간 복잡도 표기

• O(1) - 상수 시간(Contant time) : 입력 크기(n)에 상관없이 일정한 연산을 수행하는 시간 복잡도이다.
• O(log₂ n) - 로그 시간(Logarithmic time) : 입력 크기(n)이 커지면 연산 횟수가 log₂ n에 비례해서 증가하는 시간 복잡도이다.
• O(n) - 선형 시간(Linear time) : 입력크기(n)이 커지면 연산 횟수가 n에 비례해서 증가하는 시간 복잡도이다.
• O(n²) - 2차 시간(Quadratic time) : 입력크기(n)이 커지면 연산 횟수가 n²에 비례해서 증가하는 시간 복잡도이다.
• O(2ⁿ) - 지수 시간(Expotential time) : 입력 크기(n)가 커지면서 연산 횟수가 2ⁿ에 비례해서 증가하는 시간 복잡도이다.  

시간 복잡도를 줄이는 방법

1. 반복문의 숫자를 줄이자
2. 적절한 자료구조의 사용
3. 적절한 알고리즘의 이용

3. 공간복잡도(Space Complexity)

공간 복잡도란 작설한 프로그램이 얼마나 많은 메모리를 차지하는지 분석하는 방법이다.

하지만 최근 컴퓨터 성능의 비약적인 발전으로 중요성이 예전보다 많이 떨어지고 있지만, 데이터를 많이 다루는 빅데이터 분야에서는 여전히 중요한 지표로 다뤄지고 있다.

 

1. O(1) - 상수 공간 복잡도

상수 공간 복잡도는 입력 크기에 관계없이 일정한 메모리만을 사용한다.

function constantSpace(n) {
    return n * n;
}

 입력값 n의 제곱을 반환한다 이 때 사용되는 메모리 양은 입력값 n의 크기에 관계없이 항상 일정하다.

 

2.O(n) - 선형 공간 복잡도

선형 공간 복잡도는 입력 크기에 비례하여 메모리를 사용합니다.

function linearSpace(n) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(i);
    }
    return arr;
}

0부터 n-1까지의 숫자를 배열에 넣고 반환한다. 입력값 n에 따라 배열 arr의 크기가 변하므로 공간 복잡도는 O(n)이다.

 

3.O(n^2) - 2차 공간 복잡도

2차 공간 복잡도는 입력 크기의 제곱에 비례하여 메모리를 사용한다.

function quadraticSpace(n) {
    let matrix = [];
    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
            matrix[i].push(j);
        }
    }
    return matrix;
}

위 함수는 n x n 크기의 2차원 배열을 생성하며, 이 때 공간 복잡도는 O(n^2)이다.