점근석 분석
점근적 분석은 함수의 인자가 특정 값이나 무한대로 접근할 때의 함수의 행동을 설명하는 수학적 방법이다.
컴퓨터 공학에서는 알고리즘을 실행 시간이나 공간 사용량이 입력 크기에 따라 어떻게 증가하는지를 기준으로 분류한다. => 시간복잡도, 공간복잡도 계산에 활용할 수 있다.
빅오 표기법(Big O notation)
간단히 말해, 빅오는 어떤 함수 f(x)의 성장률이 다른 함수 g(x)의 성장률에 비해 같거나 느리다는 것을 의미한다.
빅오 외에도 빅세타, 빅오메가가 있으나 빅오를 사용하는 이유는 알고리즘 설계 시 최악 복잡도를 고려해야 하기 때문이다.
최악의 경우 = 즉 어느 상한선까지 같거나 그 이하로 증가하는지를 알아야 한다.
- 빅 오(O): f(x)의 성장률이 g(x)에 비례하여 증가하거나 그 이하로 증가한다. 상한선을 의미한다.
- 빅 세타(Θ): 즉, f(x)의 성장률이 g(x)와 증가율이 같다.
- 빅 오메가(Ω): f(x)의 성장률이 g(x)에 비례하여 증가하거나 그 이상으로 증가한다. 하한선을 의미한다.
빅오를 이용한 복잡도 계산 방법
복잡도 계산시 빅오를 이용하여 가장 영향력이 큰 부분, 즉 가장 높은 차수만 따진다.
상수나 가장 높은 차수가 아닌 경우 그냥 아예 배제하면 빠르게 계산할 수 있다.
더보기
출처:
'Algorithm' 카테고리의 다른 글
여러가지 트리 (0) | 2023.04.16 |
---|---|
트리의 기초 (0) | 2023.04.16 |
링크드 리스트(Linked List) (0) | 2022.12.23 |
배열 (0) | 2022.12.22 |