복잡도(Complexity)

복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉜다.

• 시간 복잡도
  • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
  • 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도
  • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
  • 알고리즘을 위해 필요한 메모리의 양

보통 복잡도를 얘기했을 때 의미하는 것은 시간 복잡도를 나타낸다. 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션(Memoization) 기법이 있다.

시간 복잡도(Time Complexity)

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법은 함수의 상한만을 나타낸다.

• O(1)
  • 상수 시간(Constant Time)
• O(logN)
  • 로그 시간(Log Time)
• O(N)
  • 선형 시간
• O(NlogN)
  • 로그 선형 시간
• O(N 제곱)
  • 이차 시간
• O(N 세제곱)
  • 삼차 시간
• O(2 N제곱)
  • 지수 시간