Big O Notation

알고리즘이란, CS에서 어떠한 문제를 어떻게? 해결하기 위한 방법이고,  이 어떠한 문제를 해결하기 위한 방법은 다양합니다.

이 다양한 방법(알고리즘) 간에 효율성을 비교하기 위해 빅오(Big O) 표기법을 보통 가장 많이 사용합니다.

 

빅오 표기법은 알고리즘의 효율성을 표기해 주는 표기법이다.

 

💡 빅오 표기법(Big O Notation)이란?

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타는데 주로 사용됩니다.

각각 시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간 즉, 메모리 효율성을 의미합니다.

시간/공간 복잡도를 나타내는 방법은 점근 표기법이라고 해서 빅오(O), 빅오메가(Ω), 빅세타(Θ) 표기법이 있다.

1. Big-O Notation O(N) : 최악의 경우
2. Big-Theta Notation Θ(N) : 평균의 경우
3. Big-Omega Notation Ω(N) : 최상의 경우

빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문에 세 가지 표기법 중에 빅오 표기법을 채택해서 사용합니다.

✓ 알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적입니다.

세 번째 표기법인 최상의 경우는 그렇게 썩 유용한 정보가 아닙니다. 왜냐하면 알고리즘에 특별한 입력값을 이용하면 O(1)에 달성할 수 있기 때문입니다.

💡 빅오 표기법의 특징

1. 상수항 무시 : 빅오 표기법은 N이 충분히 크다고 가정하고, 알고리즘의 효율성 또한 N의 크기에 따라 영향을 받기 때문에 상수항은 무시한다.
   O(2N) → O(N)과 같은 상수항은 무시하고 표기한다.
2. 영향력 없는 항 무시 : 빅오 표기법은 N의 크기에 따라 영향을 받기 때문에 가장 큰 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다.
   O(N² + 2N + 1) → O(N²)와 같이 영향력이 큰 N² 이외에 항들은 무시한다.