시간 복잡도와 점근적 표기법: 알고리즘의 실행 시간 분석하기

1. 시간 복잡도란?

**시간 복잡도(Time Complexity)**는 어떤 함수나 알고리즘이 **입력값의 크기(n)**에 따라 얼마나 많은 연산을 수행하는지를 표현한 것. 다시 말해, 알고리즘이 실행되기까지 필요한 연산 스텝의 수를 의미한다.

이때 중요한 건, 정확한 시간(초)이 아니라 입력의 크기 n에 따라 시간이 어떻게 증가하는지를 분석하는 것.

---

2. 점근적 분석이란?

시간 복잡도를 분석할 때는 보통 입력값 n이 **매우 커지는 상황(무한대에 가까워질 때)**을 상정한다. 이를 점근적(Asymptotic) 분석이라 하며, 다음과 같은 특징이 있다:

• 덜 중요한 항은 무시한다
  예: f(n) = 2n² + 3n + 1 → 점근적으로 n²만 남는다.
• 계수도 무시한다
  예: f(n) = 100n² → O(n²)로 표현한다. 왜냐하면 n이 충분히 크면 계수는 상대적인 의미가 줄어들기 때문.

---

3. 시간 복잡도는 왜 파라미터에 따라 달라지나?

함수나 알고리즘은 입력값에 따라 연산 횟수가 달라질 수 있다. 예를 들어, 배열에서 특정 값을 찾는 함수는:

• 운 좋게 처음에 찾으면 → 연산 1회
• 끝까지 찾아야 하면 → 연산 n회

이렇듯 입력값과 그 값의 위치 등 상황에 따라 성능이 달라질 수 있다. 그래서 Best, Worst, Average case로 나누어 복잡도를 분석한다.

---

4. 점근적 표기법(Asymptotic Notation)

세 가지 주요 표기법이 있다:

1) Big-O 표기법: O(n) — Upper Bound (상한선)

• 최악의 상황에서의 시간 복잡도
• 보통 우리가 가장 많이 사용하는 표기법
• "이 알고리즘은 최대 이만큼 걸린다"를 의미
• 예: 선형 탐색 → O(n) (최악의 경우 끝까지 탐색)

2) Big-Ω(오메가): Ω(n) — Lower Bound (하한선)

• 최선의 상황에서의 시간 복잡도
• 예: 정렬된 배열을 탐색할 때, 처음에 찾을 수 있는 경우 → Ω(1)

3) Big-Θ(세타): Θ(n) — Tight Bound (타이트한 바운드)

• 최선과 최악이 모두 동일한 시간 복잡도를 가질 때
• 즉, 실행 시간의 상한선과 하한선이 동일한 경우
• 예: for문이 항상 n번 돈다면 → Θ(n)

🔍 Tight Bound란?
Θ(n)은 이 알고리즘의 실행 시간이 정확히 이 수준이다를 의미.
예: 어떤 알고리즘이 항상 n²만큼 도는 경우 → O(n²), Ω(n²)이 모두 성립하므로 Θ(n²)가 된다.

---

5. Binary Search의 시간 복잡도 예시

정렬된 배열에서 이진 탐색(Binary Search)은 대표적인 예시다.

• Best Case (최선): 찾으려는 값이 한 번에 가운데에 있음 → Ω(1)
• Worst Case (최악): 끝까지 반복적으로 반으로 나눠야 함 → O(log₂N)
• Average Case: 평균적으로 중앙값에서 가까운 경우 → O(logN)으로 표현하기도 함

따라서, 이진 탐색의 시간 복잡도는 보통 O(logN), Ω(1), Θ(logN) 모두로 표현할 수 있다.
상황에 따라 어떤 관점으로 설명하고 싶은지에 따라 표기법이 달라질 수 있음.

---

6. 왜 시간 복잡도를 여러 표기법으로 나타낼 수 있나?

점근적 표기법은 상황별 성능을 분석하기 위한 수단이기 때문이다.

• O는 최악의 상황을 보여줌
• Ω는 최선의 가능성을 보여줌
• Θ는 일관적인 시간복잡도를 의미

예: 정렬 알고리즘 중 삽입 정렬

• 정렬이 거의 되어 있으면 → Ω(n)
• 완전히 무작위일 때 → O(n²)
• 일반적인 경우 → Θ(n²)

---

7. 평균 시간(average time)은 보통 어떻게 표현하나?

• 평균 시간 복잡도는 보통 O 표기법으로도 표현
• 하지만 분석 시에는 수학적 기대값(E[X])을 기반으로 Θ, Ω와 같이 분석 가능
• 단, 일반적인 설명이나 문서에서는 평균도 O 표기법을 쓰는 경우가 많다
  이유는 Worst Case를 피하고 싶기 때문이기도 함

---

8. 이중 for문의 시간 복잡도 예시

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

• 바깥 루프가 n번, 안쪽 루프도 n번 → 총 n × n = n²번 실행
  → 시간 복잡도: Θ(n²)

---

9. 복합 복잡도 예시: Θ(n + m)

for (int i = 0; i < n; i++) { ... }
for (int j = 0; j < m; j++) { ... }

• 두 개의 입력 크기 n, m에 따라 각각 독립적인 연산
  → 시간 복잡도: Θ(n + m)

이 경우도 입력의 크기가 다르므로, 둘 중 큰 쪽이 지배적인 영향을 미친다.

 

---

10. 시간 복잡도 표 (오름차순)

 

표현	이름
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	2차 시간
O(2^N)	지수 시간
O(N!)	팩토리얼 시간

 

 

---

11. 왜 Big-O(Upper Bound)를 가장 자주 사용할까?

• 최악의 상황에 대한 보장이 필요하기 때문
  → 실무나 면접에서는 항상 “최악의 경우에도 이만큼이면 충분하다”는 근거가 필요함
• 안정성을 보여줌
  → 예외 상황에서도 성능이 유지된다는 의미
• 표준처럼 널리 사용됨
  → 논문, 책, 기술 문서 등 거의 모든 자료에서 Big-O 중심으로 설명

---

마무리

시간 복잡도는 단순한 수학 기호가 아니라, 알고리즘의 성능을 예측하고 판단하는 기준이다. 다양한 상황(최선, 최악, 평균)에 따라 다르게 분석할 수 있으며, 그에 맞는 점근적 표기법을 올바르게 사용하는 것이 중요하다.