알고리즘의 복잡도

• 시간 복잡도: 알고리즘의 실행 속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

  컴퓨터 저장장치 성능의 향상에 따라 시간 복잡도의 중요성이 증가

알고리즘 성능 표기법

• Big O(빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 일반적으로 사용
  • 아무리 최악의 상황이라도, 이 정도의 성능은 보장한다는 의미
• Ω(오메가) 표기법: Ω (N)
  • 알고리즘 최상의 실행 시간을 표기
• Θ(세타) 표기법: Θ(N)
  • 알고리즘의 평균 실행 시간을 표기

Big-O 표기법

O(N)

• 입력 n에 따라 결정되는 시간 복잡도 함수

• 표현식에 가장 큰 영향을 미치는 n의 단위로 표기

  $O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)$

예시

$2n^2 + 3n$

• 만약 시간 복잡도 함수가 위와 같다면, 시간 복잡도는 $O(N^2)$
• 가장 높은 차수는 $2n^2$
• 상수는($\mathbf{2}n^2$에서 $2$) 실제 큰 영향이 없으므로 무시

중요 알고리즘의 시간 복잡도