[빅오표기법] 빅오표기법이란? (Big O notation)

.

빅오표기법 정리 1

빅오표기법 정리 2

 

 

개발자로써 알고리즘을 짜야하고, 누군가가 만들어놓은 알고리즘을 자주 사용한다.

과연 그 알고리즘은 빠른 알고리즘일까?

이것을 평가하기위한 지표가 빅오표기법(Big O notation) 이다.

 

---

1. 빅오표기법이란?

상단에서 언급했듯 빅오표기법은 알고리즘이 얼마나 빠른지를 나타내는 표기법이다.

실제로 대문자 O를 사용하기에 빅.오. 표기법이라고 한다.(정말로..!)

빅오표기법은 '초' 와같은 시간단위로 속도를 세는것이 아니라 연산 횟수를 비교하기 위한것이다.

따라서 연산양이 많아질때 알고리즘에 걸리는 시간이 어떤식으로 증가하는지 알 수 있다.

 

 

2. 예시

100개의 원소를 가진 리스트를 단순탐색과 이진탐색을 각각 수행한다고 해보자.

이진탐색은 7밀리초가 걸리고

단순탐색은 100밀리초가 걸린다.

해당 결과로 놓고보면 이진탐색이 단순탐색에 비해 15배가 빠르다.

 

 

그럼 원소의 양이 증가해도 이진탐색이 15배가 빠를까?

정답은 떙! 이다.

 

 

10억개의 원소로 각각 탐색을 수행하면

이진탐색은 32밀리초가 걸리고

단순탐색은 11일이 걸린다.

해당 경우에는 이진탐색이 단순탐색보다 3천3백만배 빠르다.

 

 

단순히 알고리즘이 얼마나 걸리는지보다, 데이터가 증가할때 어떻게 증가하는지를 파악해야 한다.

바로 이것이 빅오표기법이 필요한 이유이다!

 

 

3. 빅오표기법은 최악의 실행시간을 나타낸다

이게 무슨말이냐면,

 

단순탐색의 빅오표기법은 O(n)이다.

단순탐색은 100개의 원소중 최대 100번의 추측을 수행할 가능성이 있기 때문이다.

빅오표기법은 최악의 실행시간을 나타내는 표기법이기 때문에

첫 추측부터 정답을 찾았다고 해서 O(1)이 되지 않는다는 것이다!