[Data Structure] 시간 복잡도와 빅오 표기법(big-O notation)

---

시간 복잡도 (Time Complexity)

 

복잡도란 알고리즘이 얼마나 많은 자원을 소비하는지 나타낸다. 같은 동작을 할 때 적은 자원을 소비하는 알고리즘이 성능이 좋은 알고리즘이므로 복잡도는 알고리즘의 성능, 효율성을 나타내는 척도이다.

복잡도는 시간 복잡도와 공간 복잡도로 나뉘는데, 시간 복잡도는 알고리즘의 연산 횟수를 말하고, 공간 복잡도는 알고리즘을 위한 메모리 공간을 말한다. 시간 복잡도가 커진다는 것은 연산 횟수가 늘어난다는 것이고, 공간 복잡도가 커진다는 것은 필요한 메모리 공간이 많아진다는 것이다.

컴퓨팅 메모리가 부족한 상황이 아니라면 주로 신경써야 할 것은 시간 복잡도이다. 시간 복잡도를 나타낼 때는 다양한 표기법이 사용되는데 주로 사용되는 것이 빅오 표기법이다.

 

---

빅오 표기법

 

빅오 표기법은 입력값의 크기를 $ n $ 으로 두고 해당 알고리즘에서 얼마나 많은 연산이 일어나는지 표기하는 것이다. 이때 상수, 계수 부분은 무시하고, 최고차항만 나타내며, 여러 경우의 수가 있는 경우 최악의 상황, 즉 연산이 가장 많이 일어나는 상황을 가정한다.

상수, 계수 부분을 무시하고, 최고차항만 나타내는 것은 예를 들어 어떤 알고리즘이 $ n $ 의 입력을 받았을 때 최악의 경우 $ 3n^2 +9n + 7 $ 번의 연산을 수행한다고 가정하다. 이때 $ n^2 $ 의 계수인 $ 3 $ 과 상수인 $ 7 $ , 그리고 최고차항이 아닌 $ 9n $ 은 제거하고 $ n^2 $ 만 남긴 것이 빅오 표기법에서 보는 시간 복잡도라는 것이다. 이 예시의 경우 빅오 표기법으로 해당 알고리즘의 시간 복잡도를 나타내면 $ \mathcal{O}(n^2) $ 이다.

빅오 표기법은 입력값의 크기가 $ n $ 으로 고정되어 있고, 컴퓨팅 유닛에 따라 달라질 수 있는 실행 시간이 아닌 연산 횟수를 기준으로 알고리즘을 평가하기 때문에 알고리즘끼리 시간 복잡도를 비교하는 데에 효율적인 표기법이다. 만약 실행 시간을 기준으로 측정한다면 완벽히 동일한 환경에서 측정해야 여러 알고리즘의 상대적 성능을 평가할 수 있을 것이고, 실행 시간을 측정하기 위해 직접 실행시키고 시간을 측정해야 할 것이다.

 

---

성능 비교

 

출처: https://www.savemyexams.com/

 

빅오 표기법으로 나타냈을 때 일반적으로는 위 표와 같은 성능이 나타난다. 즉 일반적으로 연산 횟수만 보면 아래와 같다.

$$ \mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2 ) < \mathcal{O}(2^n ) < \mathcal{O}(n!) $$

연산 횟수가 많으면 성능이 떨어지는 것이기 때문에 연산 횟수의 역순으로 성능이 좋다고 본다.

 

---

예시 | Python

 

• $ \mathcal{O}(1) $ | 상수

입력값의 크기에 영향을 받지 않고, 언제나 일정 횟수의 연산을 하는 경우이다. 예를 들어 충돌이 없이 해시 테이블에서 특정 값을 찾는 것이나, 배열에서 특정 인덱스로 접근하는 것, 스택에서 push, pop 연산 등이 이에 해당한다. 나타낼 때는 $ \mathcal{O}(1) $ 로 나타냈지만, 어떠한 입력값에도 1억 번 계산하는 알고리즘 역시 시간 복잡도는 $ \mathcal{O}(1) $ 이다.

def constant_example(n):
    return n + 1

 

• $ \mathcal{O}(\log n) $ | 로그

연산이 진행될 때 마다 처리하는 데이터의 크기가 절반으로 감소하는 경우이다. 대표적인 경우가 이분 탐색이다.

def log_example(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

 

• $ \mathcal{O}(n) $ | 선형

입력값이 증가하는 만큼 선형적으로 연산이 증가하는 경우이다. 중첩 없는 단일 for 문이 대표적이다.

def linear_example(arr):
    total = 0
    for num in arr:
        total += num
    return total

 

• $ \mathcal{O}(n \log n) $ | 선형 로그

입력값이 증가하는 만큼 로그 배만큼 연산이 증가하는 경우이다. 예를 들어 배열을 나누고 병합하는 병합 정렬이 있다. 효율적인 알고리즘의 실질적인 마지노선이라 볼 수 있다. 이보다 연산이 많아지는 다항 함수, 지수 함수, 팩토리얼의 경우 입력값이 증가하면서 연산이 기하급수적으로 증가하기 때문이다.

def linear_log_example(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    sorted_arr = linear_log_example(left) + middle + linear_log_example(right)
    return sorted_arr

 

• $ \mathcal{O}(n^2) $ | 다항

입력값이 증가하는 만큼 연산이 급수적으로 증가하는 경우이다. 선형 함수가 중첩되어 있는 경우가 많다. 대표적인 것이 중첩된 for 문이다. 단일 for 문이 선형 함수인데 중첩되면 선형 함수의 제곱이므로 다항 함수가 된다.

def polynomial_example(arr):
    num = 1
    for i in range(len(arr)):
        for j in range(len(arr)):
            num *= arr[i] * arr[j]
    return num

 

• $ \mathcal{O}(2^n ) $ | 지수

입력값이 증가하는 만큼 연산이 기하급수적으로 증가하는 경우이다. 피보나치 수열을 재귀적으로 구현할 때가 대표적인 예시이다.

def exponential_example(n):
    if n <= 1:
        return n
    else:
        return exponential_example(n - 1) + exponential_example(n - 2)

 

• $ \mathcal{O}(n!) $ | 팩토리얼

입력값의 팩토리얼만큼 연산이 필요한 경우이다. 가장 대표적인 모든 가능한 순열을 탐색하는 브루트 포스 알고리즘이 팩토리얼 시간 시간 복잡도를 가진다.

def factorial_example(arr):
    if len(arr) == 0:
        return [[]]
    perms = []
    for i in range(len(arr)):
        element = arr[i]
        remaining_elements = arr[:i] + arr[i+1:]
        for p in factorial_example(remaining_elements):
            perms.append([element] + p)
    return perms

 

---

빅오 표기법 단점 및 주의점

 

• 최악의 경우만 고려한다.

기본적으로 빅오 표기법은 최악의 경우만 고려한다. 즉 일반적인 경우나 최선의 경우에 어떤 알고리즘이 더 연산이 적은지는 빅오 표기법 하나만으로는 알 수 없다. 예를 들어 퀵 정렬의 경우 최악의 경우 시간 복잡도는 $ \mathcal{O}(n^2) $ 이다. 그러나 일반적으로 퀵 정렬은 $ \mathcal{O}(n \log n) $ 의 시간 복잡도를 가진다. 최악의 경우만 고려한다면 시간 복잡도가 $ \mathcal{O}(n^2) $ 인 버블 정렬과 다를 바 없을 것 같지만, 일반적인 경우 퀵 정렬이 압도적으로 연산이 적다.

• 상수와 계수를 무시하고, 최고차항만 고려한다.

상수와 계수를 무시하기 때문에 빅오 표기법으로 같은 시간 복잡도를 가지는 알고리즘끼리는 비교할 수 없다. 예를 들어 실제 연산이 $ 2n $ 번 일어나는 알고리즘 $ A $ 와 실제 연산이 $ 100n + 200 $ 번 일어나는 알고리즘 $ B $ 의 시간 복잡도는 연산 횟수가 50배 이상 차이나는 실제와 다르게 빅오 표기법으로 나타낼 시 $ \mathcal{O}(n) $ 으로 같다.

• 입력 크기가 큰 경우에 더 유용하다.

입력값의 크기를 $ n $ 으로 놓고 연산 횟수를 비교하는 것이 빅오 표기법이기 때문에 입력 크기가 클 때 일반적인 연산 횟수인 $ \mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2 ) < \mathcal{O}(2^n ) < \mathcal{O}(n!) $ 가 성립한다. 때문에 입력값의 크기가 작은 경우에는 연산 횟수가 반대일 수 있다. 극단적으로 예를 들어서 연산이 $ 10000 $ 번 일어나는 알고리즘 $ A $ 와 연산이 $ n! $ 번 일어나는 알고리즘 $ B $ 가 있다고 가정하자. 빅오 표기법으로 나타낸다면 알고리즘 $ A $ 의 시간 복잡도는 $ \mathcal{O}(1) $ 이고 알고리즘 $ B $ 의 시간복잡도는 $ \mathcal{O}(n!) $ 이다. 따라서 일반적인 경우라면 당연히 $ B $ 가 효율적이지만, 입력값이 작은 경우라면, 즉 $ n! $ 이 $ 10000 $ 보다 작은 경우라면 $ A $ 가 연산 횟수가 적고 더 효율적이다.

• 공간 복잡도를 고려해야 한다.

시간 복잡도만 나타낼 때는 주의해야 한다. 빅오 표기법은 공간 복잡도 역시 표현할 수 있지만, 대부분의 경우 빅오 표기법으로 표기한 복잡도는 시간 복잡도이다. 즉 공간 복잡도는 고려하지 않은 경우가 많다. 이 경우는 컴퓨팅 환경에 따라 빅오 표기법으로 표기된 시간 복잡도를 기준으로 알고리즘을 선택할 수 없다. 예를 들어 컴퓨팅 메모리가 제한된 상황에서 배열을 정렬해야 한다고 가정하자. 카운팅 정렬에 경우 미리 메모리 공간에 가능한 수를 배열로 담아두고, 각 수를 카운팅해서 정렬한다. 시간 복잡도는 언제나 $ \mathcal{O}(n) $ 으로 시간 복잡도만 본다면 정렬 알고리즘 중 가장 효율적이지만 미리 메모리 공간에 가능한 모든 수를 배열로 담아두어야 하기 때문에 입력값이 커지면 어마어마한 메모리 공간이 필요하게 된다. 따라서 시간 복잡도로는 가장 효율적으로 보이는 카운팅 정렬은 컴퓨팅 메모리가 제한된 상황에서 사용할 수 없고, 그 외 정렬 알고리즘을 사용해야 한다. 이처럼 실제 상황에서는 빅오 표기법으로 나타난 시간 복잡도 외 다양한 환경을 고려해서 사용할 알고리즘을 선택해야 한다.

• 실제 연산 시간을 나타내지는 않는다.

빅오 표기법으로 나타낸 시간 복잡도는 이론적 성능을 평가하는 척도로는 유용하지만, 실제 연산 시간을 비교할 때는 여러 요소들이 영향을 미치므로 부정확하다. 실제 연산이 일어날 때는 하드웨어, 캐시, 데이터 구조 등 다양한 변수가 있고, 컴파일 언어의 경우 컴파일러의 성능이 영향을 미치기도 한다. 따라서 빅오 표기법을 통한 성능 비교를 알고리즘의 절대적 성능 비교라고 생각하면 안된다.