시간 복잡도 Big-O (O), Big-Ω (Ω), Big-Θ (Θ)

🧠 시간 복잡도 표기법 총정리

✅ 1. 표기법의 목적별 분류

표기법	이름	의미	무엇을 나타내는가?
Big-O (O)	빅오	최악의 시간	가장 오래 걸리는 경우. 성능의 상한을 보장
Big-Ω (Ω)	빅오메가	최선의 시간	가장 빨리 끝나는 경우. 성능의 하한을 나타냄
Big-Θ (Θ)	빅세타	평균/정확한 시간	실제 시간 복잡도가 상한=하한일 때. 정확한 경계

 

---

✅ 2. 시간 복잡도 유형별 분류 (O, Ω, Θ는 모두 해당 가능)

복잡도	유형	표기의미	예시 알고리즘
상수 시간	O(1)	입력 크기와 무관	해시맵 조회, 배열 인덱스 접근
로그 시간	O(log n)	반씩 줄이기	이진 탐색
선형 시간	O(n)	한 번 순회	단순 for문, 선형 탐색
로그-선형 시간	O(n log n)	분할+정복	병합 정렬, 퀵 정렬 평균
2차 시간	O(n²)	이중 루프	버블 정렬, 삽입 정렬
지수/팩토리얼	O(2ⁿ), O(n!)	매우 비효율적	순열, 백트래킹 전체 탐색

 

---

✅ 3. 예제와 함께 세 가지 표기법 적용

// 예: 배열에서 특정 값 찾기
for (int i = 0; i < n; i++) {
    if (arr[i] == target) break;
}

분석기준	표기	설정
최선	Ω(1)	첫 번째 값이 target일 경우
최악	O(n)	target이 배열 마지막이거나 없음
평균	Θ(n)	target이 중간쯤 있을 확률이 높음

 

 

---

✅ 4. 빅오, 빅오메가, 빅세타 관계도

시간 복잡도 실제 함수 T(n)이 다음 범위 안에 있음:

         Ω(g(n))         Θ(g(n))         O(g(n))
          └────┬────┘     └────┬────┘     └────┬────┘
          최소한 g(n)     정확히 g(n)     최대 g(n)

• 예를 들어 T(n) = 3n + 2이라면:
  • O(n): 최대 n에 비례해서 걸릴 수 있음
  • Ω(n): 최소 n에 비례해서 걸림
  • Θ(n): 정확히 n에 비례해서 걸림

---

📌 정리 요약

구분	의미	표기 예시	사용 목적
시간 복잡도 유형	알고리즘이 입력에 따라 얼마나 자원(시간)을 쓰는지	O(1), O(n), O(n²) 등	알고리즘 성능을 계량화
경계 표기법	최악/최선/평균 성능 분석 도구	O(n), Ω(n), Θ(n)	상황별 분석, 정확도 판단