Big-O 표기법은 알고리즘의 시간 복잡도를 나타내는 표기법으로 O(f(n))으로 나타낸다. 시간 복잡도는 알고리즘 내 연산의 횟수와 관련 있다.
즉, 예를 들면 다음과 같다.
*f(n) = n² + 2n + 3*
*g(n) = n²*
이라고 가정하면 *f(n) ≤ k * g(n)* 이 성립하는 k값이 존재하기 때문에 알고리즘 *f(n)*은 Big-O표기법을 사용하여 **O(n²)**으로 나타내는 것이다.
알고리즘 내에서 시간 복잡도를 구할 때 단위 연산의 횟수를 기준 함수로 한다. 쉽게 얘기하면 알고리즘 내에서 Big-O를 구할 때 루프와 recursion 횟수를 확인하면 된다.
<aside> 💡 Big-O 계산법은 루프의 차수(깊이)와 직결!
</aside>
🚦 Big-O표기법을 사용하는 이유?
Big-O 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다!!
다른 표기법들의 기준은 다음과 같다.
제한 시간이 1초인 문제의 경우
