빅오(Big-O) 표기법 완전 정복: 시간복잡도와 공간복잡도 분석하는 법

빅오(Big-O) 표기법 완전 정복: 시간복잡도와 공간복잡도 분석하는 법

알고리즘을 공부하면서 가장 많이 마주치는 개념이 바로 빅오(Big-O) 표기법입니다. 하지만 많은 개발자들이 단순히 O(n)이나 O(n²) 정도만 외우고 정확한 의미나 적용 방법을 이해하지 못한 채 넘어가곤 하죠.

이번 글에서는 빅오 표기법의 개념부터, 시간복잡도와 공간복잡도를 실제 코드에 적용하는 방법, 그리고 코딩테스트나 면접에서 활용하는 팁까지 차근차근 설명드리겠습니다.

---

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

빅오 표기법은 알고리즘의 성능(효율성)을 수학적으로 표현하는 방법입니다.
입력 데이터의 크기 n에 따라 알고리즘이 시간을 얼마나 소모하는지(시간복잡도), 또는 **얼마나 많은 메모리를 사용하는지(공간복잡도)**를 표현하죠.

🔎 왜 필요할까?

• 코드가 동작하는 “속도”를 정량적으로 판단할 수 있음
• 입력 데이터가 커질수록 성능 저하를 예측하고 개선 가능
• 면접 및 실무에서 알고리즘 선택의 기준이 됨

---

⏳ 시간복잡도(Time Complexity) 예시별 분석

다음은 **입력 크기(n)**에 따라 시간이 어떻게 변하는지를 나타낸 표입니다.

표기법 의미 예시 알고리즘

O(1)	상수	리스트 인덱스 접근
O(log n)	로그	이진 탐색
O(n)	선형	단순 반복 (for i in range(n))
O(n log n)	선형로그	병합정렬, 퀵정렬
O(n²)	이차 (제곱)	중첩 반복문 (이중 for문)
O(2ⁿ)	지수	피보나치(재귀, 메모이제이션 없이)
O(n!)	팩토리얼	순열 생성, 완전 탐색 문제 등

---

✅ 빅오 분석 방법: 직접 코드로 분석해보기

반응형

1. O(1) – 상수 시간 복잡도

def get_first_element(arr):
    return arr[0]  # 항상 1번만 연산

2. O(n) – 선형 시간 복잡도

def print_all(arr):
    for element in arr:
        print(element)  # n개의 요소 출력 → n번 실행

3. O(n²) – 이중 반복문

def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)  # n * n = n²번 출력

4. 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

→ 매번 탐색 범위를 절반으로 줄임 → O(log n)

---

💾 공간복잡도(Space Complexity) 분석 예시

시간복잡도처럼, **얼마나 많은 공간(메모리)**을 사용하는지도 중요합니다.

def sum_list(arr):
    total = 0        # O(1) 공간
    for num in arr:  # O(1) 공간
        total += num
    return total

→ 추가 메모리 없이 합만 저장 = O(1)

def copy_list(arr):
    copied = []         # O(n) 공간
    for num in arr:
        copied.append(num)
    return copied

→ 새로운 리스트를 하나 더 생성 = O(n)

---

⚠️ 빅오 분석 시 주의사항

• 상수는 버린다: O(2n) → O(n), O(n + 100) → O(n)
• 큰 항만 남긴다: O(n² + n + 1) → O(n²)
• 중첩 반복문 주의: 반복문이 중첩될수록 복잡도가 급격히 증가
• 재귀 함수는 콜 스택도 고려해야 공간복잡도 분석 가능

---

🎯 빅오 vs 실시간: 어떤 게 더 중요할까?

• 실제로는 실행 시간보다 빅오가 더 중요할 때가 많습니다.
  • 입력이 10만, 100만이 넘어가면 실행 시간 차이는 극명해집니다.
  • 예: O(n²)는 10,000개 입력에선 1억 번 연산 필요 → 비실용적
• 단, 입력 크기가 작다면 O(n)과 O(log n)의 차이는 미미할 수 있습니다.

---

📌 결론 및 요약

• 빅오 표기법은 알고리즘 성능을 판단하는 핵심 도구입니다.
• 시간복잡도와 공간복잡도를 모두 고려해야 최적의 코드 작성 가능
• 코드 작성 후에는 반드시 “입력 크기 n에 따라 연산 횟수가 어떻게 변하는가?”를 분석해 보세요.

👉 다음 글에서는 배열과 연결리스트의 구조적 차이와 실제 코드 비교를 통해 효율적인 자료구조 선택 방법을 알아보겠습니다!

---

📚 참고자료 및 출처

• 『알고리즘 문제 해결 전략』 (구종만 저)
• MIT OpenCourseWare: Introduction to Algorithms
• Big-O Cheatsheet