시간 복잡도

알고리즘의 실행 시간(연산 횟수)을 나타내는 척도로, 입력 크기에 대한 함수로 표현한다.
주로 점근적 분석을 통해 실행 시간을 단순하게 표현하며 이 때 점근적 표기법으로 표현한다.

점근적 표기법

시간복잡도를 표현하는 3가지 주요 표기법은 다음과 같습니다.

• Big-O ($O$, 빅오): 상한선 (Upper Bound)

  • “아무리 오래 걸려도 이 정도 시간보다는 덜 걸린다”는 최악의 경우를 표현할 때 주로 사용합니다.
  • 예: $O(N)$

• Big-Omega ($\Omega$, 빅오메가): 하한선 (Lower Bound)

  • “아무리 빨라도 이 정도 시간은 걸린다”는 최선의 경우를 표현할 때 사용합니다.
  • 예: $\Omega (1)$

• Big-Theta ($\Theta$, 빅세타): 타이트한 경계 (Tight Bound)

  • 상한선($O$)과 하한선($\Omega$)이 같을 때 사용합니다. 즉, 가장 정확한 표기입니다.
  • 예: $\Theta (N)$