[자료구조] 시간 복잡도 / Big-O (빅오)

1. 시간 복잡도란?

시간 복잡도(T(n))란 입력 크기 n에 따라 알고리즘이 수행하는 연산 횟수를 수학적으로 표현한 것이다.
실제 걸리는 시간 대신 연산 횟수를 기준으로 하는 이유는 하드웨어나 언어 차이에 따라 실행 시간이 달라지기 때문이다.

---

2. 시간 복잡도 표기 예시

시간 복잡도 함수 T(n)	최고차항인 수	계수 제거 후	Big-O 표기
2n - 1	2n	n	O(n)
2n² + 1	2n²	n²	O(n²)
(3/2)n² + (3/2)n + 1	(3/2) n²	n²	O(n²)
log₂ n (또는 log n)	log n	log n	O(log n)

 

빅오 표기법은 입력 크기가 커질 때의 증가율(성장 속도) 만을 표현하기 때문에, 상수항이나 낮은 차수 항은 무시한다.

---

3. 연산의 종류

1. 할당 연산: a = b, b = c
2. 산술 연산: +, -, *, /
3. 비교 연산: >, >=, <, <=, ==, !=
4. 논리 연산: &&, ||, !
5. 비트 연산: &, !, ^, ~, <<, >>
   (비트를 단위로 계산)

---

4. 시간 복잡도 계산의 특징

모든 입력의 경우를 계산할 수 없으므로 최악의 경우(최대 연산 횟수)를 기준으로 계산한다.
이는 알고리즘의 실행 시간이 절대로 이 이상을 넘지 않음을 보장하기 위함이다.

---

5. Big-O(빅오)란?

빅오는 시간 복잡도의 증가율을 나타내는 점근적 표기법으로,
입력 n이 커질 때 함수가 어떻게 성장하는지 보여준다.

---

6. 빅오 표기법 기준

1. 계수(상수)는 제거한다.
2. 최고차항만 남긴다.
3. Big-O로 감싼다.

참고로 최선·평균을 나타내는 Ω, Θ 표기법도 있지만
실무에서는 보통 최악 시간 복잡도(Big-O) 를 주로 사용한다.