Big-O 표기법

🧮 Big-O 표기법이란?

Big-O 표기법은 알고리즘의 시간 또는 공간 복잡도를 수학적으로 분석하기 위해 사용하는 표기법이다. 주로 입력 크기 n이 매우 커질 때, 알고리즘의 실행 시간이 어떻게 증가하는지를 설명한다.

---

✅ 핵심 개념

• 입력 크기 n이 커질수록 알고리즘의 실행 시간이 어떻게 증가하는지를 나타냄
• 실제 수행 시간보다 성장률(growth rate) 에 집중
• 정확한 연산 횟수 대신, 가장 빠르게 증가하는 항만 남기고, 상수는 무시

---

📌 Big-O 계산 예시

예시 1: n(n-1)/2

T(n) = n(n-1)/2 = (n^2 - n)/2

• 가장 높은 차수인 n^2만 남기고, 상수와 낮은 차수는 무시
• ⇒ O(n²)

예시 2: 3n + 100

• 상수 제거 → 3n
• 상수 계수 제거 → n
• ⇒ O(n)

---

💡 왜 사용하는가?

• 서로 다른 알고리즘을 비교할 수 있다
• 하드웨어나 환경에 따라 달라지는 실행 시간을 일반화된 수학적 표현으로 설명할 수 있다
• 효율적인 알고리즘 선택에 도움이 된다

---

📊 자주 등장하는 Big-O

표기법 의미

O(1)	입력 크기와 무관 (상수 시간)
O(log n)	로그 시간 (이진 탐색 등)
O(n)	선형 시간
O(n log n)	병합 정렬, 퀵 정렬 평균
O(n²)	버블 정렬, 선택 정렬, 삽입 정렬 등
O(2ⁿ), O(n!)	매우 느린 알고리즘

---

📝 정리

• Big-O는 알고리즘의 성능을 간단하고 직관적으로 표현하기 위한 수학적 도구이다.
• 계산 횟수가 많아질수록 실제 시간보다 증가 속도에 집중한다.
• 효율적인 코드를 작성하고, 다양한 알고리즘을 비교할 수 있는 기준이 된다.