시간 복잡도(Time Complexity)

문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

• 문제를 해결하는 데 시간이 얼마나 걸리느냐
• 주로 시간 복잡도를 다룬다.

공간 복잡도(Space Complexity)

문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

• 문제를 해결하는 데 메모리를 얼마나 차지하는냐

평균 시간 복잡도(Average Time Complexity)

임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

• 평균적으로 걸리는 시간

최악 시간 복잡도(Worst-case Time Complexity)

가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

• 가장 오래걸리는 시간

Big-O Notation

점근 표기법(asymptotic notation)의 하나