[자료구조/알고리즘 이론] 복잡도

복잡도란 알고리즘의 효율성을 평가하는 중요한 척도입니다. 오늘 설명할 시간복잡도는 알고리즘이 수행되는데 소요되는 시간, 공간복잡도는 알고리즘이 수행되는데 소요되는 메모리의 양을 의미합니다.

 

사실 요즘 시대에 공간복잡도는 시간복잡도만큼 그 중요도가 높지 않습니다. 무어의 법칙이라는 게 있죠? (반도체 메모리의 용량은 1년지 지날 때마다 2배씩 증가한다.) 현시대에 컴퓨터의 메모리 기술이 급속도로 성장함에 따라 알고리즘에서의 메모리 사용 효율성인 공간복잡도의 중요도는 과거에 비해 많이 낮아졌습니다.

 

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 입력 크기 n에 따라 얼마나 오래 걸리는지를 측정하는 척도입니다. 보통은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 나타냅니다. 이를 수학적으로 표기할 때, 주로 빅오 표기법(Big-O Notation, O(N))을 사용합니다. 

 

시간 복잡도의 유형

시간 복잡도의 값이 작은 것부터 나열하였습니다.

 

1. 상수 시간 O(1) (Constant Time)

- 입력 크기 n과 관계 없이 항상 같은 시간이 걸리는 알고리즘입니다.

- 아래의 코드는 어떤 숫자가 들어가도 단 한 번만 연산을 수행하기 때문에 O(1)입니다.

- 배열의 특정 요소에 접근하는 경우가 대표적인 예입니다.

void function test(int n) {
    System.out.println(n)
}

2. 로그 시간 O(logn) (Logarithmic Time)

- 입력 크기 n이 커질 때 연산 횟수가 logN이 비례해서 증가합니다.

- 입력 크기 n이 커질수록 실행 시간이 느리게 증가합니다.

- 이진탐색 알고리즘을 사용하는 경우 로그 시간이 소요됩니다.

- 아래의 알고리즘의 경우 i 값이 2배씩 증가합니다. 이를 K번 반복하면 2^K = N 이 되고 해당 수식에 로그를 씌우면 K = logN이 됩니다.

for(int i = 1; i <= N; i * 2) {
    ...
}

3. 선형 시간 O(n) (Linear Time)

- 입력 크기 n이 커질 때 연산 횟수가 n에 비례하여 증가합니다.

- 연산 횟수가 선형적으로 증가합니다.

- 배열의 모든 요소를 방문하는 경우 선형 시간이 소요됩니다.

- 아래의 알고리즘의 경우 N값만큼 방문합니다. N이 커짐에 따라 연산 횟수가 비례하여 증가합니다.

for(int i = 0; i < N; i++) {
    ...
}

4. 로그 선형 시간 O(nlogn) (Linearithmic Time)

- 입력 크기 n이 커질 때 연산 횟수가 n * logn에 비례하여 증가합니다.

- 퀵 정렬, 병합 정렬 알고리즘의 경우 로그 선형 시간이 소요됩니다.

 

5. 2차 시간 O(n^2) (Quadratic Time)

- 입력 크기 n이 커질 때 연산 횟수가 n ** 2에 비례하여 증가합니다.

- 버블 정렬, 선택 정렬 알고리즘의 경우 2차 시간이 소요됩니다.

- 아래의 알고리즘의 경우 중첩 for문으로 인해 n * n 만큼 연산을 수행합니다.

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        ...
    }
}

6. 지수 시간 O(2^n) (Exponential Time)

- 입력 크기 n이 커질 때 연산 횟수가 2**n에 비례하여 증가합니다.

- 입력크기가 커짐에 따라서 실행 시간이 급격하게 증가하는 알고리즘입니다.

- 재귀적 접근을 통한 피보나치수열 해결 문제의 경우 지수 시간이 소요됩니다.

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

7. 팩토리얼 시간 O(n!) (Factorial Time)

- 실행 시간이 입력 크기 n의 팩토리얼에 비례하여 증가합니다.

- 브루트포스(완전탐색) 접근을 통한 외판원 문제 해결의 경우 팩토리얼 시간이 소요됩니다.

 

소요시간을 시각적으로 나타낸 빅오 알고리즘 그래프입니다.

O(nlogn) 알고리즘부터 Bad로 나타낸 것을 확인할 수 있습니다. 알고리즘 문제를 풀 때 시간제한 조건을 잘 확인한 후 적합한 시간복잡도 알고리즘을 선택하여 사용하는 것이 바람직합니다.

 

소요되는 시간을 기준으로 오름차순 정렬하였습니다.

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

 

공간 복잡도(Space Complexity)

시간복잡도와 다르게 시간이 아닌 메모리의 양을 측정하는 것 외에 기본적인 개념은 같습니다. 입력 크기에 n에 따라 메모리 사용량이 변합니다.

 

공간 복잡도의 유형

공간 복잡도 값이 작은 것부터 나열하였습니다.

 

1. 상수 공간 O(1)

- 입력 크기와 무관하게 항상 같은 메모리 공간을 사용하는 알고리즘입니다.

- 단순한 변수 사용이 해당됩니다.

 

2. 로그 공간 O(logn)

- 메모리 사용량이 로그 함수에 비례하여 증가하는 알고리즘입니다.

- 재귀 호출 스택을 사용하는 재귀적 이진 탐색이 해당됩니다.

 

3. 선형 공간 O(n)

- 메모리 사용량이 입력 크기에 비례하여 증가하는 알고리즘입니다.

- 새로운 배열을 생성하는 경우가 해당됩니다.

 

4. 다항 공간 O(n^c)

- 메모리 사용량이 입력 크기의 다항식에 비례하여 증가하는 알고리즘입니다.

- 다차원 배열을 사용하는 경우가 해당됩니다.

 

5. 지수 공간 O(2^n)

- 메모리 사용량이 지수 함수에 비례하여 증가하는 알고리즘입니다.

- 재귀적 피보나치 계산을 하는 경우가 해당됩니다.

 

시간 복잡도 표현 방법

시간 복잡도는 오메가(Omega), 세타(Theta), 빅오(Big-O), 총 3가지 표기법을 사용해 나타낼 수 있습니다.

간단하게 말하면 오메가는 최선의 경우의 소요되는 시간, 세타는 평균적/정확하게 소요되는 시간, 빅오는 최악의 경우 소요되는 시간을 나타냅니다.

 

그럼 평균적이고 소요시간을 나름대로 정확하게 나타내는 세타 표기법을 사용하는 게 더 좋지 않나?라고 생각할 수 있지만.. 그렇게 단순하게 생각하고 넘어갈 문제가 아닙니다.

 

오메가 표기법

입력 크기 n에 대해 최선의 경우 실행 시간이 최소 어떻게 증가하는지를 설명합니다. 한마디로 낙관적인 상황에서의 알고리즘 소요시간을 계산합니다. 알고리즘이 최소한 어느 정도의 성능을 보장할 수 있는지를 평가할 때 사용합니다.

세타 표기법

입력 크기 n에 대해 최악의 경우와 최선의 경우 실행 시간 모두를 정확하게 설명합니다. 두 상황 모두를 고려하여 알고리즘 소요시간을 계산하기 때문에 비교적 정확하며, 알고리즘의 실행 시간이 특정 함수와 비례할 경우 사용합니다.

빅오 표기법

입력 크기 n에 대하여 최악의 경우 실행시간이 최대 어떻게 증가하는지 설명합니다. 즉 비관적인 상황에서의 알고리즘 소요시간을 계산합니다. 알고리즘 성능이 어떤 상황에서도 최대한으로 얼마나 나빠질 수 있는지를 평가할 때 사용합니다.

 

빅오를 사용하는 이유

이쯤 되면 왜 세타, 오메가 표기법 대신 빅오 표기법을 시간 복잡도에 널리 사용되는지 이해하셨을 것 같습니다.

 

1. 빅오 표기법은 최악의 상황에서의 알고리즘 수행 시간을 다루기 때문에, 어떠한 상황에서도 주어진 시간 안에 완료될 것이라는 보장을 제공합니다. 이러한 소요시간에 대한 보수적인 접근으로 높은 신뢰성을 제공합니다. 실시간 시스템/응용 프로그램에서 매우 중요합니다.

 

2. 위의 이유로 빅오 표기법은 산업 표준이 되어 대부분의 알고리즘 분석, 교육, 문서 등에서 빅오 표기법을 활용하고 있습니다.

 

3. 알고리즘이 얼마나 빠르게 최악의 시나리오의 속도로 느려질 수 있는가? 를 표현한다는 점에서 간단하고 직관적입니다.

 

세타 표기법은 비교적 정확한 소요 값을 제공할 수 있지만, 평균 분석을 위해 알고리즘이 다양한 분석에 대해 어떻게 동작하여 시간이 얼마나 소요되는지에 대한 깊은 이해가 수반되어 실제로 적용하기엔 어려울 수 있습니다.

오메가 표기법의 경우엔 먼저 최선의 상황은 드뭅니다. 최선의 상황이길 빌며 오메가 표기법을 적용하는 것은... 좀 웃기지 않나요? 따라서 일반적인 성능 평가에 적합하지 않을 수 있습니다.

 

시간 복잡도 계산법

빅오 표기법은 계수, 상수 없이 최고차항만 표기하면 됩니다.

 

아래의 연산은 total += arr[i], for을 통한 반복문으로 이루어져 있습니다. for문 내부의 연산은 한 번씩만 이루어집니다. for문을 통한 반복 연산은 n번 이루어집니다. 따라서 연산 횟수를 표현하는 함수는 n으로, 시간복잡도는 O(n)이 됩니다.

def example1(arr):
    total = 0
    for i in range(len(arr)): # n번
        total += arr[i] # 1번
    return total

아래의 연산의 경우 두 개의 중첩반복문과 반복문 내의 연산으로 이루어져있습니다. 반복문 연산 n번 * 반복문 연산 n번 + 반복문 내부 연산과 n번으로 계산할 경우 n^2 + n의 결과가 나오게 됩니다. 따라서 시간복잡도는 O(n^2)가 됩니다.

def example2(matrix):
    sum = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            sum += matrix[i][j]
    return sum

 

1초에 컴퓨터가 가능한 연산은 1억번 입니다. 이 점을 잘 고려해서 시간 복잡도를 계산한 후, 본인의 알고리즘이 시간 제한에 걸리지 않는지 체크하는 것도 좋은 방법일 것 같습니다!

 

References

https://medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966

코드의 시간 복잡도 계산하기

https://joyhong-91.tistory.com/12#calBO

[algorithm] 시간복잡도란? 시간복잡도 계산하는법 ( O(1), O(n), O(log n))

https://yoongrammer.tistory.com/79

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)