Big-O 표기법

🧠 왜 Big-O 표기법을 배워야 할까?

알고리즘 성능을 비교하는 방법들:

1. 직관적 표현 ("A가 B보다 조금 빠르다")

   • 모호하고 주관적입니다.
   • 비교 기준이 명확하지 않아 객관적인 판단이 어렵습니다.

2. 실제 코드 실행 시간 비교

   • 사용하는 PC의 성능, 운영체제, 백그라운드 프로세스 등에 따라 결과가 달라집니다.
   • 환경 의존적인 방법입니다.

3. 입력 크기에 따른 성능 차이

   • 입력이 작을 땐 문제 없어 보이지만, 입력이 커지면 알고리즘 간 성능 차이는 크게 벌어질 수 있습니다.

✅ 그래서 등장한 것이 바로 Big-O 표기법입니다.

---

🔍 Big-O 표기법이란?

입력 크기 n이 커질수록 성능이 어떻게 변화하는지를 함수로 표현하는 방식입니다.

예시:

• O(1) : 입력 크기와 관계 없이 일정한 시간
• O(n) : 입력이 늘어나면 그에 비례하여 처리 시간도 늘어남
• O(n^2) : 입력이 두 배가 되면, 연산량은 네 배로 증가

---

⚙️ Big-O 표기법 적용하는 2단계 원칙

✅ 1단계: 대략적인 연산 횟수 계산

코드나 알고리즘을 보고 얼마나 많은 연산이 수행되는지 대략적으로 판단합니다.

예시:

• 1 → 상수 시간
• n + 1 → 선형 증가
• n^2 + 1 → 제곱에 비례한 증가

✅ 2단계: “대장만 남긴다” (가장 영향력 있는 항만 남김)

규칙 1️⃣: 가장 큰 항만 남기기

• 작은 성장은 무시하고 가장 빠르게 증가하는 항만 남깁니다.

규칙 2️⃣: 상수는 무시

• 입력 크기가 커질수록 상수의 영향은 미미해지므로 생략합니다.

예시:

O(1 + n + 4 + n^2 + 1)  
→ O(n^2)

---

📈 대표적인 시간 복잡도 예시

시간 복잡도	의미	예시 알고리즘
O(1)	상수 시간	배열의 인덱스로 접근
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	배열 전체 순회
O(n log n)	로그 선형 시간	병합 정렬, 퀵 정렬 평균
O(n^2)	이차 시간	이중 for문, 버블 정렬

위 이미지는 이러한 시간 복잡도 곡선이 입력 크기 n이 커질수록 얼마나 차이가 나는지를 시각적으로 보여줍니다.

---

📚 로그 함수란?

Big-O 표기에서 자주 등장하는 log n의 개념을 이해해 봅시다.

✅ 로그의 기본 개념

• 2^1 = 2
• 2^2 = 4
• 2^3 = 8
  ⇒ 이렇게 거듭제곱한 결과를 b라고 했을 때, log₂(b)는 그 지수를 의미합니다.

즉,

log₂(n)은 "2를 몇 번 곱해야 n이 되는가?"를 의미합니다.

---