[알고리즘] 시간 복잡도 & 공간 복잡도

코드스테이즈 41기 교육 내용을 정리하고 있습니다.
틀린 부분이 있으면 댓글로 알려주시면 감사하겠습니다

시간 복잡도

 

백준 문제 14003번 문제입니다.

알고리즘 문제를 풀다보면 시간제한이 걸려 있는 경우가 있습니다. 대수롭게 생각하지 않고 풀다가 시간 초과로 실패한 경우도 있을 겁니다. 이는 시간 복잡도를 고려하지 않았기 때문에 실패한 경우라 볼 수 있습니다.

시간 복잡도를 고려한다는 것은 입력값의 변화에 따라 연산을 실행 할때, 연산 횟수에 비해 시간이 얼마 만큼 걸리는가 입니다.

 

시간 복잡도를 표기하는 방법은 Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)로 표기합니다. 각각은 최악, 최선, 평균을 뜻하는데 이 포스팅에서는 가장 많이 사용하는 Big-O만 고려할 예정입니다.

O(1)

 

코드스테이츠

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법입니다. O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다. 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미입니다. O(1)의 시간 복잡도를 갖는 알고리즘입니다.

function indexOne(arr) {
    return arr[1];
}

let arr = [1, 2, 3, 4, 5];
let result = indexOne(arr);
console.log(result); // 2

위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있습니다. 예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있습니다.

O(n)

코드스테이츠

O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다. 예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있습니다. O(n)의 시간 복잡도를 가진 알고리즘을 살펴보겠습니다.

function arrayLog(arr) {
    for(el of arr){
        console.log(el)
    }
}

let arr = [1, 2, 3, 4, 5];
arrayLog(arr);

O(log n)

코드스테이츠

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.

이분 탐색과 같이 경우의 수를 반으로 줄게 하는 경우 다음과 같은 시간 복잡도를 갖습니다.

O(n²)

코드스테이츠

O(n2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.

function doubleFor(arr) {
    for(el of arr){
        for(e of arr){
            console.log(el,':',e)
        }
    }
}

let arr = [1, 2, 3, 4, 5];
doubleFor(arr);

다음 알고리즘에서 for문 안에 똑같은 for문이 들어가 삼중 for문이 되는 경우 O(n³)만큼 시간 복잡도를 갖지만 O(n2)로 표기합니다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기합니다. 

O(2^n)

코드스테이츠

O(2n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

즉, 입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어야 합니다. 그러나 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하세요.

대략적인 데이터 크기에 따른 시간 복잡도는 다음과 같습니다.

코드스테이츠

공간복잡도

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미합니다. 즉 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미합니다.

 

프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구합니다. 여기서 집중해야 할 부분은 가변적인 공간입니다. 왜냐하면 고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않기 때문입니다. 그러나 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줍니다.

 

보통 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문에 알고리즘 구현 시 공간 복잡도에 실패했다면, 보통은 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정했을 경우가 많을 것이니 그것부터 확인해야 합니다.

 

그러나 때에 따라 공간 복잡도를 중요하게 보는 경우가 있는데, 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우가 바로 그 경우입니다.