점근적 표기법

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

big-Θ표기법이란, 어떤 알고리즘을 실행함에 있어서, 실행 횟수인 n이 충분히 커졌을 때의 근접한 한계값

big-Θ표기법을 사용하는 것은 실행 시간에 대해 점근적으로 위, 아래에 근접한 한계값이 있다고 표현하는 것

"점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문

"근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻

---

함수들의 증가도 비교 그래프

커지는 속도가 느린 순서부터 나열한 점근적 표기법

---

Big-Θ 표기법은 실행 시간에 대하여 위아래에 점근적으로 근접한 한계가 있지만 한계를 위에만 둘 때도 있음

때로는 "실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있음. 이런 경우를 위해 "big-O" 표기법을 사용

---

때로는 알고리즘이 상한선 없이 최소한 어느 정도 걸린다고 해야 할 때도 있음

그럴 때 사용하는 것이 big-Ω 표기법

여기서 Ω는 그리스 문자 "오메가"를 의미함