[Algorithm] 시간 복잡도 (Time Complexity)

🟩 시간 복잡도(Time Complexity)란?

알고리즘이 입력 크기에 따라 얼마나 많은 시간을 소요하는지를 나타내는 척도.

즉, 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.

일반적으로, 입력 데이터의 크기가 커질수록 알고리즘의 실행시간이 어떻게 증가하는지를 분석하여 효율성을 평가하는데 사용한다.

 

시간 복잡도는 보통 빅오 표기법(O)을 사용하여 표현한다.

예를 들어, O(n)이라면 입력 크기 n에 비례하는 시간을 소요한다는 의미이다. 

---

🟩 시간 복잡도 표현 방법

시간 복잡도는 보통 점근 표기법(Asymptotic Notation)으로 사용된다.

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

점근 표기법 - 위키백과, 우리 모두의 백과사전

 

주로 사용되는 3가지 점근 표기법은 빅오 표기법(O), 오메가 표기법 (Ω), 세타 표기법 (θ) 이다.

간단하게 이에 대해 설명해 보자면,

 

빅 오 표기법(O, Big-O Notation)

- 알고리즘의 성능 상한을 나타낸다.

- 입력 크기가 커질 때, 최악의 경우에도 실행시간이 이 값 이하로 유지된다는 것을 보장한다.

- 주로, 최악의 상황에서 얼마나 시간이 소요되는지를 분석하는데 사용된다.

- 예를 들어, $O(n^2)$ 알고리즘은 입력 크기 n이 커지면 실행 시간이 최대 $n^2$에 비례해서 증가한다.

 

오메가 표기법(Ω, Big-Omega Notation)

- 알고리즘의 성능 하한을 나타낸다.

- 입력의 크기가 커질 때, 최상의 경우에도 실행시간이 이 값 이상이 될 수밖에 없다는 것을 의미한다.

- 가장 좋은 상황에서도 얼마나 시간이 소요되는지를 분석할 때 사용한다.

- 예를 들어, $\Omega(n)$  알고리즘은 입력 크기 $n$이 커지면 실행 시간이 최소한 $n$에 비례해서 증가한다.

 

세타 표기법(θ, Big-Theta Notation)

- 알고리즘의 성능을 정확히 설명한다.

- 입력 크기 n이 커질 때, 실행시간은 $\theta(f(n))$  에 정확히 비례한다.

- 주로 알고리즘의 성능을 정확하게 알고 싶을 때 사용한다.

- 예를 들어 $\theta(n \log n)$ 알고리즘은 입력 크기 n이 커지면 실행 시간이 $n \log n$ 에 정확히 비례하여 증가한다.

 

요약하자면 

• 빅 오 표기법(O) : 최악의 경우 상한 (알고리즘의 성능 한계)
• 오메가 표기법(Ω) : 최상의 경우 하한 (알고리즘의 성능 최소치)
• 세타 표기법(θ) : 알고리즘의 성능을 정확히 설명 (상한과 하한이 동일한 경우)

---