컴퓨터 과학 분야에서, 알고리즘 복잡도의 종류를 구분하는 표기법.
입력에 크기에 따라 알고리즘 실행 비용(복잡도)이 어떻게 증가하는지를 표현하는 방법이다. 입력의 크기가 n일 때, 입력이 커짐에 따라 계산비용이 어떤 함수 f(n)의 상수곱을 넘지 않으면 O(f(n))이라고 표기한다.
O : order of the function
종류
많이 등장하는 종류만 정리해 봄
- O(1)
- O(n)
- O(n log n)
- O(n**2)
- O(n**k)
- O(k**n)
- O(n!)
Reference