알고리즘의 복잡도

• 시간 복잡도(Time Complexity)
  • 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
  • 평균 시간 복잡도(Average Time Complexity): 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
  • 최악 시간 복잡도(Worst-case Time Complexity): 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
• 공간 복잡도(Space Complexity)
  • 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계
• Big-O Notation
  • 점근 표기법(asymptotic notation)의 하나
  • 어떤 함수가 증가 양상을 다른 함수와의 비교로 표현(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
  • $O(n)$, $O(n^2)$....
• 선형 시간 알고리즘 - $O(n)$
• 이차 시간 알고리즘 - $O(n^2)$