빅오표기법 Big-O

빅오표기법이란

Mathematical notation that describes algorithm efficiency

알고리즘의 성능을 수학적으로 표현한 것

 

Time & Space complexity

시간, 공간 복잡도를 알 수 있음

 

Describes the growth rate of algorithms

알고리즘의 실제 러닝 타임을 표시하는 것보다 데이터와 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표라 상수는 무조건 1이 된다.

 

빅오 표기법은 최악의 경우에 대한 것으로 단순 탐색이 절대로 O(n)의 시간보다 느려지지 않는다 !

 

---

 

예시

 

 

중요한점

상수는 버린다 ! Drop constants

빅오표기법은 실제 알고리즘의 러닝타임을 재기위한게 아니라 장기적으로 데이터가 증가할 때 철회시간을 예측하기 위해 만들어진 표기법이기 때문이다.

따라서 증가하지 않는 숫자는 무시하겠다는 것.

 

 

 

https://youtu.be/6Iq5iMCVsXA