[CS] 알고리즘 01 : 알고리즘 표기법

Big-O 표기법

Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간 복잡도를 가진다는 의미이다.
즉, 알고리즘에 필요한 시간의 상한선을 의미한다.

O(1)
O(log n)
O(N)
O(nlog n)
O(n²)

Big-Ω

Big-O와 반대되는 개념으로 최선의 경우를 뜻한다.
즉, 알고리즘에 필요한 시간의 하한선을 의미한다.
예를들어 숫자 28을 선형 탐색으로 찾으려고 할 때
[28, 6, 4, 23]이라면 한번에 찾을 수 있다.

Ω(1)
Ω(log n)
Ω(N)
Ω(nlog n)
Ω(n²)