빅오 표기법(Big-O Notation): 알고리즘 성능 분석의 핵심 개념

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

1. 빅오 표기법(Big-O Notation)의 정의

빅오 표기법(Big-O Notation)은 알고리즘의 성능을 분석하고 입력 크기(n)에 따라 실행 시간이 어떻게 변화하는지를 수학적으로 표현하는 방법입니다. 이는 컴퓨터 과학에서 알고리즘의 효율성을 평가하는 중요한 도구로 사용됩니다.

✅ 빅오 표기법의 주요 특징:

• 최악의 경우(Worst Case) 성능을 기준으로 분석
• 입력 크기(n)가 증가할 때 알고리즘 실행 시간이 어떻게 변하는지를 표현
• 상수 계수(Constant Factor)와 낮은 차수의 항은 무시
• 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity) 분석에 사용

📌 빅오 표기법은 알고리즘의 실행 속도를 직관적으로 비교할 수 있도록 도와줍니다.

---

🔹 빅오 표기법의 주요 시간 복잡도 유형

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

✅ 입력 크기(n)에 관계없이 일정한 시간이 걸리는 알고리즘

✔️ 예제:

def get_first_element(arr):
    return arr[0]  # 첫 번째 요소 반환 (항상 O(1))

📌 해시 테이블 조회, 배열의 특정 인덱스 접근 등이 O(1) 시간 복잡도를 가집니다.

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

✅ 입력 크기가 증가할수록 실행 시간이 느리게 증가하는 알고리즘

✔️ 예제:

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

📌 이진 탐색(Binary Search)과 같은 알고리즘이 O(log n) 복잡도를 가집니다.

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

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

✔️ 예제:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

📌 리스트 탐색(순차 검색)과 같은 알고리즘이 O(n) 복잡도를 가집니다.

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

✅ 입력 크기가 증가할수록 실행 시간이 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)

📌 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)과 같은 정렬 알고리즘이 O(n log n) 복잡도를 가집니다.

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

✅ 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘

✔️ 예제:

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]

📌 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort) 등이 O(n²) 복잡도를 가집니다.

6. O(2ⁿ) - 지수 시간(Exponential Time)

✅ 입력 크기가 증가할수록 실행 시간이 급격히 증가하는 알고리즘

✔️ 예제:

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

📌 재귀적 피보나치(Fibonacci) 알고리즘이 O(2ⁿ) 복잡도를 가집니다.

7. O(n!) - 계승 시간(Factorial Time)

✅ 입력 크기가 증가할수록 실행 시간이 극단적으로 증가하는 알고리즘

✔️ 예제:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

📌 외판원 문제(Travelling Salesman Problem, TSP)와 같은 최적화 문제에서 O(n!) 복잡도가 나타납니다.

---

📌 결론

✅ 빅오 표기법(Big-O Notation)은 알고리즘의 실행 속도를 분석하는 핵심 개념입니다.
✅ O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!) 순으로 성능이 감소합니다.
✅ 알고리즘의 시간 복잡도를 최적화하면 실행 속도와 성능을 향상할 수 있습니다.
✅ 효율적인 알고리즘을 선택하고, 필요에 따라 최적화를 수행해야 합니다.