컴퓨터 공학/알고리즘
Big-O notation
seungyoon
2021. 2. 9. 18:12
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)이 한계라는 의미이다.