빅오(Big-O) 표기법 정리

 

빅오(Big-O) 표기법과 알고리즘 효율성 분석

빅오(Big-O)는 알고리즘의 성능을 분석하고 효율성을 평가하기 위한 수학적 표기법으로, 입력값이 커질 때 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 표현한다.
이를 통해 알고리즘이 대규모 데이터에서도 얼마나 효율적으로 작동하는지, 성능의 상한선을 분석할 수 있다.

 

 

빅오란?

빅오 표기법은 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다.

• 이 표기법은 가장 최악의 경우(worst-case)를 기준으로 알고리즘의 성능을 표현하며, 알고리즘의 성장률을 이해하는 데 유용하다.
• 이를 통해 입력 데이터 크기(n)가 증가함에 따라 실행 시간 또는 메모리 사용량이 어떤 식으로 변할지 예측할 수 있다.

 

 

빅오 표기법의 종류와 예시

1. O(1): 상수 시간

• 입력값이 아무리 커져도 실행 시간은 일정
• 특징: 알고리즘이 입력 크기와 무관하게 일정한 작업만 수행한다. 가장 효율적인 알고리즘 중 하나이다.
• 예시: 해시 테이블의 조회 및 삽입
   

# O(1) 예시: 해시 테이블 조회
my_dict = {'a': 1, 'b': 2}
value = my_dict['a']  # 항상 일정한 시간에 수행

 

 

2. O(log n): 로그 시간

• 입력값이 증가해도 실행 시간이 느리게 증가하며, 매우 큰 입력값에도 견고하다.
• 특징: 한 번 탐색할 때마다 입력값의 크기를 절반으로 줄이는 구조이다.
• 예시: 이진 검색 (Binary Search)
   

# O(log n) 예시: 이진 검색
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

 

 

3. O(n): 선형 시간

• 입력값의 크기만큼 실행 시간에 영향을 받는다.
• 특징: 모든 입력값을 한 번 이상 확인해야 하는 작업에서 나타난다.
• 예시: 정렬되지 않은 리스트에서 최대값 찾기

# O(n) 예시: 최대값 찾기
def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

 

 

4. O(n log n): 로그 선형 시간

• 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)과 같은 대부분의 효율적인 정렬 알고리즘이 해당한다.
• 특징: 입력 데이터를 나누고(분할) 다시 합치며(병합) 처리하는 과정에서 발생한다.
   
• 예시: 병합 정렬

# O(n log n) 예시: 병합 정렬
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left + right
    return result

 

 

5. O(n²): 이차 시간

• 실행 시간이 입력값의 제곱에 비례한다.
• 특징: 이중 반복문을 사용하는 알고리즘에서 자주 나타난다.
• 예시: 버블 정렬(Bubble Sort)
   

# O(n²) 예시: 버블 정렬
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

 

 

6. O(2ⁿ): 지수 시간

• 입력값이 조금만 증가해도 실행 시간이 기하급수적으로 늘어난다.
• 특징: 입력값의 크기 변화에 따라 실행 시간이 급격히 증가한다. 비효율적이며 대규모 데이터에서는 사용할 수 없다.
• 예시: 재귀를 사용해 피보나치 수열 계산
   

# O(2ⁿ) 예시: 피보나치 수열
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)