BIG-O는 알고리즘의 효율성을 나타내는 지표이다 BIG-O를 이용해 알고리즘의 성능을 판단한다. BIG-O 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.
시간 복잡도는 알고리즘의 시간 효율성을 의미한다. 시간이 늘어나는 패턴을 추상화로 표기한 것으로 함수의 시간 소요를 일반화하는 것이다.
표기법
BIG-O 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받는다. 그렇기 때문에 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다. 입력값(n) 표기는 제한이 없다.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
f(n) = 3n + n² + 5위와같이 수학적 표기로 예를 든다면 영향력이 있는 값은 n² 이다. 상수항은 무시한다.
O(2n) -> O(n)위와 같이 영향력이 없는 상수항 2를 무시하고 O(n) 으로 표기한다.
O(N² + 3N + 3) -> O(N²)영향력이 없는 항은 무시한다. O(N²)으로 표기한다.
O(1) vs O(n)
O(1)
castant time 일정한 패턴을 말한다. 입력값(n)의 크기와 상관없이 항상 일정한 시간 패턴을 보이는 것은 O(1)이라고 표기한다. 예를들어, 시간이 오래 걸리든 빨리 걸리든 시간이 일정한 패턴을 보인다면 O(1)이다.
O(n)
일정하게 증가하는 패턴을 말한다. 입력값(n)의 크기에 따라 시간 패턴이 일정하게 늘어나는 것을 O(n)이라고 표기한다. 예를 들어, 데이터 구조 길이가 시간이 오래 걸린다면 O(n)이다.
O(log n) vs O(n²)
O(log n) logarithmic
증가하는 속도가 줄어들면서 증가하는 패턴을 말한다. 이진 트리탐색을 예로 들 수 있다. 트리와 같은 구조로 자식이 2개 이하로만 존재하고 일정한 규칙으로 뻗어나가기 때문에 순서가 있는 데이터 구조로 정리되어 있다. 그렇기 때문에 첫 시행 후 반이 버려지고 또 탐색하고, 반이 버려지는 것을 반복한다면 시간 패턴은 점점 줄어들면서 진행되는것을 보인다. 이와 같은 패턴을 O(log n)이라고 한다.
O(n²)
증가하는 속도가 점점 급격히 증가하는 패턴을 말한다. 버블 정렬을 예로 들 수 있다. 2중 for 문을 사용하면서 정렬이 되어 있지 않은 요소들을 하나하나 탐색해야 할 때 같은 패턴을 O(n²)이라고 한다.
