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

알고리즘을 평가하는 두 가지 요소는 시간 복잡도 (Time Comlexity)와 공간 복잡도 (Complexity)로 나뉜다. 이 두 가지는 속도와 메모리 사용량을 평가하는 것인데, 알고리즘의 수행 시간 분석 결과를 시간 복잡도라 하고 메모리 사용량에 대한 분석 결과를 공간 복잡도라고 한다. 프로그램을 짤 때에는 항상 worst case를 고려해야한다. 그렇기 때문에 시간 복잡도와 공간 복잡도는 보통 Big-Oh 표기법을 이용해서 나타낸다.
ㅤ

1. 시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘의 수행 시간 분석 결과이다. 시간 복잡도를 평가할 때에는 먼저 연산의 횟수를 세고, 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 만든다.

시간 복잡도는 다음과 같이 3가지로 나뉘는데, 일반적으로 Big-Oh 표기법을 사용하여 시간 복잡도를 나타낸다.
ㅤ

Best Case (최상의 경우)

• Big-Omega 표기법 사용
• 최상의 경우로, 최소로 걸리는 시간을 의미한다.

Worst Case (최악의 경우)

• Big-Oh 표기법 사용
• 최악의 경우로, 최대 오래 걸리는 시간을 의미한다.

Average Case (평균적인 경우)

• Big-Theta 표기법 사용
• 평균적인 경우로, 평균적인 시간을 의미한다.
  ㅤ

위 사진은 시간 복잡도 그래프인데, 일반적으로 시간 복잡도가 O(nlogn) 정도는 되어야 알고리즘 성능이 의미있다고 말할 수 있다.

시간 복잡도 순서는 다음과 같다.

Know Thy Complexities!
ㅤ

Big-Oh 표기법 (Notation)

함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ K에 대하여 f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C, K가 존재하면 f(n)의 Big-Oh는 O(g(n))이다.
수식을 보고 Big-Oh를 구하는 방법은 어렵지 않다. T(n)이 다항식으로 되어있을 경우, 최고차항의 차수가 Big-Oh가 된다. 예를 들면 다음과 같다.
ㅤ

ㅤ

시간 복잡도 계산 예제

시간 복잡도 = Sum (Frequency * step count (or step execution))

• 예제 1

    func ex1(n: Int) {
        for i in 0..<n { // n + 1
            let a = i // n
        }
    }
    // 시간 복잡도 = 2n + 1 == n

• 예제 2

    func ex2(n: Int) {
        for i in stride(from: 0, to: n, by: 2) { // (n / 1) + 1
            let a = i // (n / 2)
        }
    }
    // 시간 복잡도 = n + 1 == n

• 예제 3

    func ex3(n: Int) {
        for i in stride(from: 0, to: n * n, by: 1) { // (n^2 + 1)
            let a = i // n^2
        }
    }
    // 시간 복잡도 = n^2 + 1 + n^2 = 2n^2 + 1 == n^2

• 예제 4

    func ex4(n: Int) {
        for i in 0..<n { // n + 1
            for j in 0..<i { // {n(n+1)} / 2
                let a = i // {n(n+1)} / 2
            }
        }
    }
    // 시간 복잡도 = n^2 + 2n + 1 == n^2

  

2. 공간 복잡도 (Space Complexity)

[Algorithm] 알고리즘 공간복잡도에 대하여