[Computer Science] 복잡도 계산을 위한 빅오 표기법 (Big-O Notation) 에 대해 알아보자

코딩 테스트에서 결과물에 대한 채점을 표기할 때 주로 사용하는 빅오 표기법.

평상시에는 이에 대해서 무지하였고 알 생각도 크게 없었으나, 요즘 들어 CS 에 너무 무지했던게 아니었나 싶어 짧게나마 공부하기 위해 글을 작성해본다.

# 빅오 표기법 (Big-O Notation) 이란?

알고리즘의 시간 복잡도 및 공간 복잡도를 표현하는데 사용되는 수학적 기법.

주로 최악의 실행 시간을 표현하기 위해 사용되며 알고리즘의 성능을 입력 크기(n) 이 증가함에 따라 어떻게 변화하는지 나타낸다.

 

# 빅오 표기법 알고리즘 성능

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

 

입력 크기와 관계없이 일정한 시간이 걸리는 알고리즘

[예시] 배열의 특정 인덱스 찾기

# arr 이나 index 가 어떤 값으로 설정되더라도 배열 arr 의 특정 index 에 접근하므로 일정한 시간이 소요된다.
def get_element(arr, index):
    return arr[index]

 

 

 

2. O(n) - 선형 시간 (Linear Time)

 

입력 크기 n에 비례해서 실행 시간이 증가하는 알고리즘

[예시] 배열에서 모든 요소를 순회

# arr 의 크기가 증가할수록 for 문의 순회가 증가하므로 복잡도 증가
def sum_elements(arr):
    total = 0
    for num in arr:
        total += num
    return total

 

 

3. O(log n) - 로그 시간(Logarithmic Time)

 

입력 크기(n)가 커질수록 실행 시간이 로그 형태로 증가하는 알고리즘

[예시] 정렬된 배열에서 이진 탐색(Binary Search)

# 이진 탐색은 검색할 때마다 탐색 범위를 절반으로 줄이기 때문에 로그 형태의 시간이 소요된다.
def binary_search(arr, target):
    left, right = 0, len(arr) - 1 # 0, arr 요소 갯수 - 1 반환
    while left <= right:
        mid = (left + right)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

 

 

4. O(n²) - 이차 시간(Quadratic Time)

 

입력 크기(n)의 제곱에 비례해서 실행 시간이 증가하는 알고리즘

[예시] 버블 정렬(Bubble Sort)

# 버블 정렬의 경우 중첩된 반복문이 존재하므로 입력 크기의 제곱에 비례하여 시간이 증가한다.
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

 

 

5. O(n log n) - 선형 로그 시간(Linearithmic Time)

 

입력 크기(n)와 그 로그 값의 곱에 비례하여 시간이 증가하는 알고리즘

[예시] 병합 정렬(Merge Sort)

# 병합 정렬은 데이터를 분할하고 다시 합병하는 과정에서 n log n의 시간이 소요된다.
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr)
    left = merge_sort(arr[:mid]) # mid - 1 까지 절반 슬라이싱하여 가져옴
    right = merge_sort(arr[mid:]) # mid ~ 끝까지 슬라이싱하여 가져옴

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:]) # 리스트에 요소 추가
    result.extend(right[j:]) # 리스트에 요소 추가
    return result

 

 

6. O(2n) - 지수 시간 복잡도 (Exponential Time)

 

입력크기 N 이 증가하면 실행시간이 기하급수적으로 증가

[예시] 피보나치 수열

# O(2ⁿ)의 시간 복잡도를 가진 피보나치 예시
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 작은 숫자에도 급격히 느려짐

 

7. O(n!) - 팩토리얼 시간 복잡도 (Factorial Time)

 

입력 크기가 조금만 증가해도 팩토리얼만큼 급격히 시간이 늘어남

[예시] 순열 알고리즘

# O(n!) 예시: 순열(Permutation) 알고리즘
def permutations(arr):
    if len(arr) == 0:
        return [[]]
    
    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in permutations(rest):
            result.append([arr[i]] + perm)
    return result

print(permutations([1, 2, 3]))

 

이러한 빅오표기법의 알고리즘 성능을 그래프로 나타내면 다음과 같이 표시된다.

 

초록색 -> 효율적이며 좋은 성능

주황색 -> 보통 수준의 효율성

빨간색 -> 효율성이 떨어지는 알고리즘을 나타낸다.

 

알고리즘 성능은 O(1) ~ O(n!) 까지의 순서를 가지며 O(1) 이 가장 좋고 O(n!) 이 가장 좋지 않다.

# 빅오 표기법에 알아야하는 이유

개발자들이 특정 로직을 풀어나가기 위한 알고리즘을 구현할 때, 어느 알고리즘이 가장 효율적인지를 파악해야하는데 이러한 과정에서 빅오표기법을 주로 사용한다.

특히, 회사를 들어가기 위해서는 코딩테스트를 보는 경우가 많은데 이러한 경우 코딩테스트에 시간 제한 및 메모리 사용량에 관련하여 제한이 걸려있는 경우가 많다.

 

다음은 백준 홈페이지의 한 문제이다.

시간 제한 1초와 메모리 제한 1024MB 가 조건으로 걸려있는 것이 보인다.

이 때, 메모리 제한의 경우 매우 크기에 이를 초과하지 않을 수 있으나, 1초라는 시간 제한으로 인해 무작정 특정 알고리즘을 도입한다면 올바른 코드라고 할 지라도 시간 내에 문제 풀이가 되지 않아 실패할 수 있게 된다.

시간 제한 1초, 메모리제한 1024MB

 

이러한 상황을 대비하여 우리는 빅오표기법을 사용하는 것이고, 이 빅오 표기법을 사용함으로 인해 어떠한 알고리즘이 코드 풀이에 가장 적합한지와 효율적인 코드를 작성할 수 있는 기회를 얻게 되는 것이다.

---

사실 시간복잡도 및 공간복잡도를 알아내기 위한 방법으로는 위의 빅오표기법 (최악실행시간) 뿐만이 아닌 다른 여러가지 표기법도 존재하지만 대체적으로 Big-O Notation 을 사용하므로, 이 부분에 대해서만 알아도 큰 문제는 없을 것이다.