시간 복잡도

시간 복잡도란?

• 알고리즘의 성능을 나타내는 척도
• 동일한 기능을 수행할 때, 일반적으로 시간 복잡도가 낮을수록 우수
• 주로 빅오 표기법(Big-O Notation)으로 표현

Big-O Notaion

• 가장 빠르게 증가하는 항만을 고려하는 표기법

• 차수가 가장 큰 항에서 계수를 제외하여 표현

• 아래로 갈수록 시간 복잡도↑

  시간 복잡도	의미
  $O(1)$	상수 시간
  $O(logN)$	로그 시간
  $O(N)$	선형 시간
  $O(NlogN)$	로그 선형 시간
  $O(N^2)$	이차 시간
  $O(N^3)$	삼차 시간
  $O(2^N)$	지수 시간