알고리즘: 빅오 표기법(Big O notation)

 

 

 

---

 

 

점근석 분석

점근적 분석은 함수의 인자가 특정 값이나 무한대로 접근할 때의 함수의 행동을 설명하는 수학적 방법이다.

컴퓨터 공학에서는 알고리즘을 실행 시간이나 공간 사용량이 입력 크기에 따라 어떻게 증가하는지를 기준으로 분류한다. => 시간복잡도, 공간복잡도 계산에 활용할 수 있다.

 

 

 

빅오 표기법(Big O notation)

간단히 말해, 빅오는 어떤 함수 f(x)의 성장률이 다른 함수 g(x)의 성장률에 비해 같거나 느리다는 것을 의미한다.

빅오 외에도 빅세타, 빅오메가가 있으나 빅오를 사용하는 이유는 알고리즘 설계 시 최악 복잡도를 고려해야 하기 때문이다.
최악의 경우 = 즉 어느 상한선까지 같거나 그 이하로 증가하는지를 알아야 한다.

 

 

• 빅 오(O): f(x)의 성장률이 g(x)에 비례하여 증가하거나 그 이하로 증가한다. 상한선을 의미한다.
• 빅 세타(Θ): 즉, f(x)의 성장률이 g(x)와 증가율이 같다. 
• 빅 오메가(Ω): f(x)의 성장률이 g(x)에 비례하여 증가하거나 그 이상으로 증가한다. 하한선을 의미한다.

 

 

전공 수업 때 필기한 자료입니다.

 

 

 

 

 

빅오를 이용한 복잡도 계산 방법

복잡도 계산시 빅오를 이용하여 가장 영향력이 큰 부분, 즉 가장 높은 차수만 따진다.

상수나 가장 높은 차수가 아닌 경우 그냥 아예 배제하면 빠르게 계산할 수 있다.

 

 

 

 

---

 

출처:

빅오 표기법 (big-O notation) 이란

빅오 표기법을 설명하다. 시간과 공간의 복잡도.