[Programming] Asymptotic Bounding #01: Upper bound, Lower bound, Tight bound

Asymptotic Bounding #01: Upper bound, Lower bound, Tight bound

 

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

# Big-O Notation => Asymptoic Bounding

Data Structure를 통해 Big-O notation에 대해서 이해했다면 다음 단계로 Asymptotic  Bounding에 대해서 살펴봐야 한다. Asymptotic bounding은 한국에서 점근 표기법이라고 불리며 알고리즘의 효율성을 판단하기 위한 기준으로 사용되고 있다. 이번 포스트에서는 기본적으로 빅오 표기법을 이해하고 있다고 판단하고 포스팅을 작성하도록 하겠다.

 

# Asymptotic bounding이란?

기존 Big-O notation을 통해서 알고리즘의 효율성을 판단한다고 배웠지만 상황에 따라서 같은 경우에도 알고리즘의 효율성이 달라진다. 이를 기존에는 wrost case, best case, average case라고 부르면 배웠을 것이다. 전공자들 중에서는 외워서 알고 있는 경우도 있고 전체적으로 왜 각각이 다른 case가 나오는지 이해를 하고 있는 사람도 있을 것이다.

Asymptotic bounding은 빅오에서 발생하는 각기 다른 상황에 대해서 3가지 측면으로 나눠서 판단한다. Upper bounding, Lower bounding, Tight bounding 등으로 나눠서 구분하는데 한국에서는 뭐라고 부르는지는 필자는 모르겠다. 알고 있는 Bro가 있다면 댓글로 알려주면 감사하겠다. 이 Upper bound, Lower bound, Tight bound 등이 익숙하지는 않겠지만, 아래와 같이 다른 용어로 살펴보면 "아하"하는 부분이 있을 것이다.

Upper bound => Big O
Lower bound => Omega
Tight bound => Theta

Bio-O notation을 처음 배울때는 전부 빅오라고 배웠을 수 있지만 사실은 upeer bound가 Bio-O를 의미하며, Lower bound는 Omega, Tight bound는 Theta를 나타낸다. Asymptotic bounding에 대한 Examples이나 각각의 구체적인 설명은 다음 포스트에서 이어서 이야기를 나눠보도록 하자.

 

# Asymptotic bounding을 사용하는 이유

결과적으로 Asymptotic bounding을 왜 사용하는지에 대해서 말하자면, 알고리즘의 효율성을 확인하기 위해서이다. 빅오 표기법에서 끝나는 게 아니라 결과적으로 Asymptotic bounding에 대해서 배우기 위해서 빅오 표기법을 살짝 맛보았던 게 대학 수업에서는 Data Structure 수업이었을 것이다. Asymptotic bounding은 빅오 표기법과 완전 다른 게 아니고 응용된 버전이자 알고리즘 효율성 판단이라는 동일한 목적을 가지고 있다고 이해하면 된다. 빅오 표기법을 배울 때 애매하게 생각이 들었던 부분이 있었다면 그 이유는 아직 완벽히 다 배우지 않았기 때문이다. Asymptotic bounding을 시작으로 더 심화된 지식을 익히다 보면 알고리즘에 대한 이해도가 쑥쑥 늘 것이다.

---

# In conclusion, 3줄 요약

1. Asymptotic bounding은 Bio-O notation의 연장선이다.

2. Upper bound, Lower bound, Tight bound 등으로 나눠서 구분한다.

3. Asymptotic bounding은 알고리즘 효율성 판단하기 위한 목적으로 사용된다.

---