Big-O 란?
big-O는 알고리즘의 효율성을 나타내는 지표이다. 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ⁿ)
1
f(n) = 3n + n² + 5
위와같이 수학적 표기로 예를 든다면 영향력이 있는 값은 n² 이다.
- 상수항은 무시한다.
- example
1
O(2n) -> O(n)
위와 같이 영향력이 없는 상수항
2를 무시하고 O(n) 으로 표기한다. - 영향력이 없는 항은 무시한다.
1
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
증가하는 속도가 줄어들면서 증가하는 패턴을 한다. 이진 트리 탐색 BinarySearchTree로 예를 들 수 있다. 트리와 같은 구조로 자식이 2개 이하로만 존재하고 일정한 규칙으로 뻗어나가기 때문에 순서가 있는 데이터 구조로 정리되어 있다. 그렇게 때문에 첫 시행 후 반이 버려지고 또 탐색하고 반이 버려지는 것 을 반복한다면 시간 패턴은 속도가 점점 줄어들면서 증가하는 패턴을 보인다. 이와 같은 패턴을 O(log n)이라고 한다.
O(n²)
증가하는 속도가 점점 급격히 증가하는 패턴을 말한다. 버블 정렬을 예로 들 수 있다. 2중 for 문을 사용하면서 정렬이 되어있지 않은 요소들을 하나하나 탐색해야 할 때 같은 패턴을 O(n²)이라고 한다.
위의 Big-O의 표기는 대표적으로 많이 사용되는 표기법이다. 경우에 따라 표기법은 다양하게 존재한다. n의 표기에는 제한이 없으며, n lon n,n + k, kⁿ등 다양하게 표현할 수 있다.