Big-O란 무엇인가?

• 알고리즘 성능을 수학적으로 표기해주는 표기법
• 시간과 공간 복잡도를 표현
• 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 목표, 상수와 같은 숫자들은 모두 1이 된다.

시간복잡도

• 시간복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.
• 알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데
  • 수행시간에 해당하는 것이 시간 복잡도 Time Complexity
  • 메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity

연산 횟수를 카운팅 할때 3가지 경우가 있다.

1. 최선의 경우 Best Case
2. 최악의 경우 Worst Case
3. 평균적인 경우 Average Case

O(1)

• constant time
• 입력 데이터 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 표현

O(N)

• linear time