GitHub - ChangSuLee00/CS-study
Contribute to ChangSuLee00/CS-study development by creating an account on GitHub.
github.com
big-O
입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법.
빅오는 알고리즘의 효율성을 나타내는 표기 방식으로, 충분히 큰 입력값 n에 대한 점근적 상한선을 나타내는 방식이다.
이때 점근적 표기법(asymptotic notation)이란 알고리즘의 수행 시간을 나타낸 함수에서 중요하지 않은 항목과 상수 계수를 제거한 것이다.
따라서 빅오는 최고차항만을 표기한다.
big-O의 수학적 정의
모든 n>=n_0에 대하여 0<= f(n) <=cg(n)인 양의 상수 c,n_0가 존재하면 f(n) = O(g(n))
위 수식을 그림으로 표현하면 다음과 같이 볼 수 있다.
cg(n)은 4n이고 f(n)은 3n+2이라고 가정한다.
값을 표로 나타내면 다음과 같다.
| n | cg(n) | f(n) |
|---|---|---|
| 0 | 0 | 2 |
| 1 | 4 | 6 |
| 2 | 8 | 8 |
| 3 | 12 | 11 |
n_0의 값 2보다 큰 모든 n에 대하여 cg(n)의 값은 f(n)보다 크다.
따라서 c = 4이고, n은 2보다 크거나 같을 때 f(n)의 빅오(상한)은 g(n)이다.
빅오는 상한을 나타내기 때문에 f(n)에 대하여 n제곱이 상한이 될 수도 있지만. 한계를 측정하는데 차이가 급격하게 나는 대상을 비교하는 것을 의미가 없기 때문에 이러한 표기는 하지 않는다.
참고
- 파이썬으로 배우는 자료구조 핵심원리
- 중간바보도 배우는 알고리즘 1강 - Big O notation (대문자 O 표기법)
'Computer science > Data structure' 카테고리의 다른 글
| 자료구조 - Graph(그래프) (0) | 2023.03.23 |
|---|---|
| 자료구조 - Queue(큐) (0) | 2023.01.15 |
| 자료구조 - Stack(스택) (0) | 2023.01.15 |
| 자료구조 - 연결 리스트(Linked list) (0) | 2022.12.16 |
| 자료구조 - Array(배열) (0) | 2022.12.02 |
