1.1 복잡도 개념

• 시간 복잡도(Time Complexity)
  • 알고리즘이 입력 값에 따라 소비하는 시간의 양을 표현
  • 입력 크기가 증가할 때 알고리즘의 성능 변화를 예측이 가능
• 공간 복잡도(Space Complexity)
  • 알고리즘이 동작 과정에서 사용하는 메모리 공간의 크기를 표현
  • 알고리즘의 메모리 사용 패턴을 분석하고 최적화 작업이 가능

1.2 복잡도 표기법

1.2.1 빅오(O)

$$ T(n)=O(f(n)) $$

• 알고리즘의 최악의 시간 복잡도(upper bound)를 의미
• 특정 알고리즘의 시간 복잡도를 O(f(n))로 나타내면, 그 알고리즘이 주어진 입력 크기 n에 대해 항상 f(n)보다 적은 시간이 소요된다는 의미

1.2.2 빅오메가(Ω):

$$ T(n)=Ω(g(n)) $$

• 알고리즘의 최선 시간 복잡도(lower bound)를 의미
• 특정 알고리즘의 시간 복잡도를 Ω(g(n))으로 나타내면, 그 알고리즘이 주어진 입력 크기 n에 대해 항상 g(n)보다 많은 시간이 소요된다는 의미

1.2.3 빅세타(Θ):

$$ T(n)=Θ(h(n)) $$

• 알고리즘의 평균 시간 복잡도(average bound)를 의미
• 특정 알고리즘의 시간 복잡도를 Θ(h(n))으로 나타내면, 그 알고리즘이 주어진 입력 크기 n에 대해 상한과 하한이 모두 h(n)과 같다는 의미
• 알고리즘의 최선의 시간과 최악의 시간과 상관없이 평균적인 실행 시간을 의미

<aside> 💡 일반적인 알고리즘 연산에서 평균값에 가장 근사한 표기법은 빅세타(Θ) 입니다. 하지만, 최악의 경우에 대한 보장과 알고리즘 간의 비교를 위해 빅오(O) 표기법을 주로 사용합니다.

복잡도 표기법에서는 알고리즘의 실행 시간 함수에서 가장 큰 항만 남겨두는 것이 핵심입니다.

예를 들어 $T(n)$ = $2n^2$ + $n$ + 1의 경우, 가장 큰 항은 $2n^2$입니다. 따라서 가장 큰 항이 영향을 크게 미쳐 다른 항들은 상대적으로 무시가 될 수 있습니다.

이 함수의 복잡도 표기법은 다음과 같이 작성됩니다.

$$ T(n) = O(n^2) $$

이것은 주어진 알고리즘이 입력 크기 $n$에 대해 최대 O($n^2$)에 비례하는 시간이 소요된다는 것을 의미합니다.

</aside>