[Big Oh Notation] 빅 오 표기법이란?

 

빅 오 표기법이란?

---

알고리즘을 공부하면서 접하게되는 단어가 있습니다 바로 '빅 오(Big Oh)' 입니다. 빅 오 표기법은 알고리즘의 복잡도를 단순화할 때 사용하는 점근 표기법의 하나입니다.

 

 

 

Big Oh?

---

빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능합니다.

 

 

 

점근 표기법

---

 

 

• O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.
• o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.
• θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
• ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.
• Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

 

References

---

• https://www.boostcourse.org/cs204/lecture/480381?isDesc=false

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)