Big-O 표기법이란
빅오 표기법은 알고리즘의 효율성을 표현하기 위해 가장 많이 사용하는 표기법 중 하나이다.
알고리즘의 실행 시간 또는 공간 복잡도를 입력 크기에 대한 함수로 나타낸다.
최악의 경우를 표기하기 때문에 알고리즘 복잡도의 상한을 표현하기에 적합하다.
표기법은 아래와 같다.
O(f(n))
n은 입력 크기를 나타내고, f(n)은 알고리즘의 복잡도를 표현하는 함수이다.
그 외 표기법으로는
- Big-Ω 표기법: 최선의 경우의 복잡도를 표기.
- Big-Θ 표기법: 평균적인 경우의 복잡도를 표기.
컴퓨터공학에서는 항상 최악의 경우를 고려해야 하므로 주로 Big-O 표기법을 사용한다.
