시간 복잡도

  • 정의: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는가.
  • 알고리즘을 위해 필요한 연산의 수로 계산할 수 있음.
  • 빅오(Big-O) 표기법: 함수의 상한을 표기 (ex. $3N^3 + N^2 + 1,000,000$ => O($N^3$)으로 표기.)

공간 복잡도

  • 정의: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는가.
  • 알고리즘을 위해 필요한 메모리의 양으로 계산할 수 있음.
  • 시간 복잡도와 같이 빅오(Big-O) 표기법을 사용한다.