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

알고리즘을 공부하다 보면 반드시 등장하는 개념이 바로 빅오(Big-O) 표기법이다.
이번 글에서는 코딩 테스트와 실무에서 자주 쓰이는 빅오 표기법을 개념 → 규칙 → 종류 → 예제 순서로 깔끔하게 정리해본다.

---

빅오(Big-O) 표기법 복잡도 차트

 

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

입력 크기(n)가 증가할수록 알고리즘의 실행 시간 또는 메모리 사용량이 얼마나 증가하는지를 나타내는 표기법이다.

• 정확한 실행 시간 ❌
• 성능의 증가 추세(성장률) ⭕
• 언어, 하드웨어에 독립적

즉, "이 알고리즘이 큰 입력에서도 살아남을 수 있는가"를 판단하는 기준이다.

---

2. 왜 빅오 표기법을 사용하는가?

• 알고리즘 간 성능 비교
• 대용량 데이터 처리 가능 여부 판단
• 비효율적인 코드 사전 제거
• 코딩 테스트 시간 제한 대응

---

3. 빅오 표기법 계산 규칙

1️⃣ 상수항 제거

상수는 입력 크기 증가에 영향을 주지 않으므로 제거한다.

O(2n)   → O(n)
O(1000) → O(1)

---

2️⃣ 최고차항만 남긴다

입력이 커질수록 가장 영향이 큰 항만 고려한다.

O(n² + n + 1) → O(n²)

---

3️⃣ 순차 실행은 덧셈

여러 작업을 순서대로 실행하면 시간 복잡도는 더해진다.

O(n) + O(n²) → O(n²)

✔️ 최고차항만 남기므로 O(n²)

---

4️⃣ 중첩 반복문은 곱셈

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        // 작업
    }
}

O(n × n) = O(n²)

---

4. 대표적인 시간 복잡도 종류

🟢 O(1) – 상수 시간

입력 크기와 상관없이 항상 동일한 시간

int value = arr[0];

• 배열 인덱스 접근
• 스택 push / pop

---

🔵 O(log n) – 로그 시간

입력이 커질수록 증가 속도가 매우 느림

Binary Search

• 이진 탐색
• 균형 이진 트리 탐색

---

🟡 O(n) – 선형 시간

입력 크기에 비례

for (int i = 0; i < n; i++)
{
    // 작업
}

• 배열 전체 순회

---

🟠 O(n log n)

효율적인 정렬 알고리즘

• Merge Sort
• Heap Sort
• Quick Sort (평균)

---

🔴 O(n²) – 제곱 시간

이중 반복문 구조

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        // 작업
    }
}

• Bubble Sort
• Selection Sort
• Insertion Sort (최악)

---

⚫ O(2ⁿ) – 지수 시간

입력이 조금만 커져도 실행 시간이 폭발

• 피보나치 재귀 (메모이제이션 없음)
• 모든 경우의 수 탐색

---

☠ O(n!) – 팩토리얼 시간

가장 비효율적인 복잡도

• 모든 순열 탐색
• 브루트포스 TSP 문제

---

5. 시간 복잡도 성능 비교

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)
O(n!)

⬇️ 아래로 갈수록 실무 및 코딩 테스트에서 사용 불가

---

6. 공간 복잡도(Space Complexity)

메모리 사용량도 빅오로 표현한다.

int[] arr = new int[n]; // O(n)

• 재귀 호출 시 스택 메모리 고려
• 추가 배열 생성 여부 중요

---

7. 최선 / 평균 / 최악 시간 복잡도

• 일반적으로 최악(Worst Case) 기준으로 표기
• 예: Quick Sort
  • 평균: O(n log n)
  • 최악: O(n²)

---

8. 정리

빅오 표기법은 정확한 실행 시간이 아니라
입력이 커질 때 얼마나 효율적으로 동작하는지를 나타내는 지표다.

 

알고리즘 성능을 판단할 때 빅오는 선택이 아니라 필수다.

 

 

 

 

 

 

 

 

 

이미지 출처 :

https://velog.io/@gillog/%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84#%E2%99%82%EF%B8%8F-%EC%B0%B8%EA%B3%A0%EC%82%AC%EC%9D%B4%ED%8A%B8-%E2%99%82%EF%B8%8F

빅-오 표기법(Big-O Notation) & 시간, 공간복잡도(Time, Space Complexity)