Big-O notation

Big-O notation

---

점근적 상한 Aysmpototic Upper Bound

n ≥ N 인 모든 정수 n 에 대하여 $g(n)$ ≤ $cf(n)$이 성립하는 실수 c>0과 음이 아닌 정수 N이 존재한다.

$g(n) ∈ O(f(n))$ $g(n)$ 은 $f(n)$의 big O이다.

• $g(n)$ : 내가 구한 알고리즘/함수
• $f(n)$ : 해당 함수의 시간 복잡도를 나타내는 함수

g(n) ∈ O(f(n))

n ≥ N 인 모든 정수 n에 대하여 g(n) ≤c x f(n)이 성립하는 실수 c > 0 과 음이 아닌 정수 N이 존재한다.

• 기울기가 양수
• cf(n)과 g(n)의 교차점 N이 양의 정수로 반드시 존재한다.
• N 이후로 cf(n)은 g(n)보다 항상 큰 값을 나타낸다.
• 즉, N이후에 g(n)은 아무리 최악의 시간복잡도가 나와도 cf(n)이 한계라는 의미이다.