알고리즘 : 시간복잡도와 공간복잡도

 

효율적인 알고리즘을 만들려면

해당 알고리즘이 얼마나 많은 연산을 하는지, 연산에 필요한 공간이 얼마나 되는지를 알아야 합니다.

시간복잡도와 공간복잡도는 이러한 상황으로 인해 생겼습니다.

 

 

 

 

시간복잡도와 빅-오 표기법

시간복잡도란, 해당 알고리즘을 수행하는 데 걸리는 연산의 횟수를 말합니다.

한번의 알고리즘동안 입력값과 크기에따라 걸리는 횟수를 시간복잡도라고 합니다.

예를 들어, 길이에 상관없이 3번의 계산 이후 출력이 나오는 알고리즘이 있다면,

해당 알고리즘의 시간복잡도는 3입니다.

만약 입력값의 길이만큼의 계산을 수행하는 알고리즘이 있다면,

그 알고리즘의 시간복잡도는 n 입니다.

 

예시 코드를 보겠습니다.

// 시간복잡도 1인 함수
function print(number num){
    return num;
}


// 시간복잡도 n인 함수
function sumArray(number[] arr){
    number sum = 0;
    for(i=0;i<arr.length;i++){
        sum+=arr[i];
    }
    return sum;
}

 

print 함수의 경우 입력값을 그대로 출력합니다. 따라서 한번의 계산만을 수행하므로 시간복잡도는 1입니다.

반면, sumArray 함수의 경우 입력받은 배열의 길이만큼 시간복잡도가 변합니다.

따라서 n번의 계산을 수행하므로  시간복잡도가 n이 됩니다.

 

시간복잡도가 클수록 계산이 길어지고, 이는 곧 계산시간이 되기 때문에,

시간복잡도를 줄이는 것이 알고리즘의 최적화가 됩니다.

 

그런데, 시간복잡도를 계산하였는데, 시간복잡도가 n²+2n+1 와 같은 식이 나왔다고 하겠습니다.

심지어 n²+log₆n 와 같은 복잡도가 나왔다면 어떨까요?

여기서 하나 알아둬야 할 점은, 값이 커질수록 최대차수의 값을 제외하곤 고려할 필요가 없다는 것입니다.

예를 들어 n²+2n+1 로 계산을 해본다면

n = 2 일때는 4 + 4 + 1이고

n = 10 일때는 100 + 20 + 1이며,

n = 1000 일때는 1000000 + 2000 + 1 이 됩니다.

만약 n = 10000000... 이면 결국 최대차수의 값을 제외하곤 매우 작은값이 되어버리게 됩니다.

따라서 우리는 최대차수를 제외하고 나머지를 모두 생략하는 표기법을 사용할 것입니다.

이를 빅-오 표기법이라고 합니다.

 

 

빅-오 표기법은 최대차수가 되는 식을 제외한 계수와 다른 식들을 생략합니다.

시간복잡도가 2n 이든, 3n이든 O(n)으로 통일하는거죠.

마찬가지로 n²+2n+1 과 n²+log₆n 모두 O(n²)가 됩니다.

빅-오 표기법을 통해 복잡한 시간복잡도 또한 간략하게 알 수 있게 됩니다.

 

 

 

 

공간복잡도

공간 복잡도는 해당 알고리즘을 수행하는 데 필요한 총 용량을 의미합니다.

예전에 비해 현대에는 기술의 발전으로 용량의 제한이 줄어들었기 때문에 시간복잡도에 비해 중요도가 많이 떨어진 느낌이지만,

적은 용량을 활용하여 문제를 해결해야하는 경우 시간복잡도보다 더 중요해질 수도 있습니다.

 

할당하는 변수 하나를 1이라 표현한다면,

길이 n인 배열을 n,

길이 n × n 배열을 n² 으로 표기합니다

 

여기에, 재귀함수가 존재한다면, 재귀함수가 몇번 실행되는지 또한 공간복잡도에 영향을 줍니다.

1의 용량을 가진 함수를 n번 실행한다면 1×n = O(n),

n의 용량을 가진 재귀함수를 n번 실행한다면 n×n = O(n²)

 

이런식으로 말입니다.

 

다만 전체적인 계산 시간과 용량을 줄일 수도 있지만

시간복잡도를 줄이기 위해 공간을 할당하거나,

공간복잡도를 줄이기 위해 복잡한 계산식을 사용하는 등

서로 반비례하는 방법을 택해야 하는 경우도 있기 때문에,

어떤 상황에서 어떤 알고리즘을 사용하는지가 중요합니다.