22.01.15(토)

금주 학습했던 Big-O 표기법에 대해 정리하고자 한다.

---

Big-O

• 시간, 공간의 복잡도를 수학적으로 표시하는 방법이다.
• 알고리즘의 최악의 실행 시간을 표기하며, 이는 아무리 최악의 상황이라도 이정도의 성능은 보장한다는 의미이다.
  (input 데이터 증가율에 따른 알고리즘 성능을 예측하기 위해 사용됨.)
  (복잡도는 빠른 순서대로 정리)

표기형태

O(1) (Constant)

• 데이터의 입력 크기에 상관없이, 언제나 일정한 시간이 걸리는 알고리즘을 나타냄.
  (데이터 입력크기가 상관없으므로, 데이터가 얼마나 증가하든 성능에 영향 X)

O(log₂ n) (Logarithmic)

• 데이터의 입력 크기가 커질 수록 처리 시간이 로그만큼 짧아지는 알고리즘을 나타냄.
  (데이터가 10배 증가하면, 처리 시간은 2배)

O(n) (Linear)

• 데이터의 입력 크기와 처리 시간이 정비례 하여 증가하는 알고리즘을 나타냄.
  (데이터가 10배 증가하면, 처리 시간은 10배)

O(n log₂ n) (Linear-Logarithmic)

• 데이터의 입력 크기와 처리 시간이 로그배 만큼 증가하는 알고리즘을 나타냄.
  (데이터가 10배 증가하면, 처리시간은 약 20배)

O(n²) (quadratic)

• 데이터의 입력크기가 n배 증가할수록 처리시간이 n*n배 증가하는 알고리즘을 나타냄.
  (데이터가 10배 증가하면, 처리시간은 100배)

O(2ⁿ) (Exponential)

• 데이터의 입력크기가 증가할수록 기하급수적 처리시간이 증가하는 알고리즘을 나타냄. horrible!!

O(n!) (Factorial)

• 데이터의 입력크기가 증가할수록 기하급수적 처리시간이 증가하는 알고리즘을 나타냄. horrible!!