[Algorithm] 시간 복잡도와 공간 복잡도

[시간 복잡도(Time complexity)]

자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 표현하는 방식.

보통 Big-O 표기법을 사용한다.

수치가 작을수록 효율적인 알고리즘이지만 문제에 따라 O(2^n) 또는 O(n!)등의 복잡한 알고리즘을 사용해야만 하는 경우도 존재한다.

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

 

함수를 설계할 때 최대 O(n log n)정도의 시간 복잡도를 가지게 하는 것이 바람직하다.

각 시간 복잡도를 그래프로 표현한 사진.

O(1) - 상수

n에 관계없이 일정한 시간이 걸리는 알고리즘.

대부분의 경우에서 가장 단순하고 빠르다.

stack의 push/pop 연산, 배열/큐 등의 원소에 대한 접근 등이 이에 해당한다.

function foo(n) {
	return n + 1;
}

위 함수는 n에 관계없이 일정한 시간이 소요되므로 시간 복잡도는 O(1)이다.

O(log n) - 로그

n이 증가함에 따라 소요 시간이 로그 함수 형태로 증가하는 알고리즘.

각 단계마다 실행 횟수가 반으로 줄어들기 때문에 n의 크기가 커져도 일정 수준의 효율을 보장한다.

이진 탐색(Binary search) 알고리즘 등이 이에 해당한다.

function foo(n) {
    while(n >= 0) {
    	n = n / 2;
    }
    return n;
}

위 함수는 n의 크기에 따라 대략 2/n번 실행되므로 시간 복잡도는 O(log n)이다.

O(n) - 선형

n이 증가함에 따라 소요 시간이 선형 함수 형태로 증가하는 알고리즘.

소요 시간이 n의 크기에 정비례한다.

단순 반복문, 선형 탐색(Selection sort) 알고리즘 등이 이에 해당한다.

function foo(n) {
    for(let i = 0; i < n * 2; i++){
    	console.log("Hello world! " + i);
    }
}

위 함수는 n의 크기에 따라 n에 정비례한 횟수만큼 실행되므로 시간 복잡도는 O(n)이다.

O(n log n) - 선형 * 로그

n이 증가함에 따라 소요 시간이 선형 * 로그 함수 형태로 증가하는 알고리즘.

소요 시간이 n과 n의 로그 시간의 곱에 비례한다.

병합 정렬(Merge sort) 알고리즘 등이 이에 해당한다.

function foo(n) {
    while (n >= 0) {
    	for(let i = 0; i < n * 2; i++){
        	console.log("Hello world! " + i);
        }
        n = n / 2
    }
}

위 함수는 O(log n) 함수 안에서 O(n)함수가 실행된다. 따라서 시간 복잡도는 O(n log n)이다.

O(n^2) - 제곱

n이 증가함에 따라 소요 시간이 n의 제곱만큼 증가하는 알고리즘.

소요 시간이 n의 제곱에 비례한다.

O(n^3), O(n^4)등 n의 상수 배 제곱은 모두 O(n^2)로 표현한다.

다중 반복문, 삽입 정렬(Insertion sort), 거품 정렬(Bubble sort), 선택 정렬(Selection sort) 알고리즘 등이 이에 해당한다.

function foo(n) {
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            console.log(i + "," + j);
        }
    }
}

위 함수는 O(n) 함수 안에서 O(n) 함수가 실행된다. 따라서 시간 복잡도는 O(n log n)이다.

O(2^n) - 지수

n이 증가함에 따라 소요 시간이 2의 n승 그래프에 비례해 증가한다.

재귀 함수로 구현한 피보나치 함수 등이 이에 해당한다.

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

위 함수는 실행될 때마다 똑같은 함수가 2번 더 실행되므로 시간 복잡도는 O(2^n)이다.

O(n!) - 팩토리얼

n이 증가함에 따라 소요 시간이 n의 팩토리얼에 비례하게 증가하는 함수.

일반적으로 최악의 시간 복잡도.

계산 시간이 기하급수적으로 늘어나는 것을 이용해 암호화 알고리즘에 활용하기도 한다.

function foo(n) {
    if (n <= 1) {
    	return 1;
    }
    return n * foo(n - 1);
}

위 함수는 n의 팩토리얼을 구하는 함수이다. 1 * 2 * 3 * ... * (n - 1) * n회 실행되므로 시간 복잡도는 O(n!)이다.

 

---

 

[공간 복잡도(Space complexity)]

한 개체의 실행부터 종료까지 필요한 메모리 공간의 정도를 나타낸다.

 

총 필요 공간은 고정 공간과 가변 공간의 합이다.

 

고정 공간 - 입/출력에 관계없이 요구되는 공간

개체가 실행될 때 메모리에 할당된 후 개체가 종료될 때까지 증가, 감소, 삭제되지 않는다.

• 코드 저장 공간
• 단순 변수
• 고정 크기의 구조 변수
• 고정 크기의 구조 상수 등

가변 공간 - 프로그램 실행 중 동적으로 요구되는 공간

스택(stack)과 힙(heap) 영역에서 필요에 따라 할당되고 해제된다.

• 동적 배열
• 트리 구조
• 재귀 함수 호출 스택 등