What is BigO?
BigO 노테이션은 알고리즘 실행 효율성을 측정하는 방법이다. 데이터 입력값의 크기에 따라 알고리즘 실행 속도의 변화를 설명할 수 있다.
BigO 시간복잡도 구별
1) Constant Time — O(n)
constant time이 걸리는 경우는 input data의 크기와 관계없이 항상 같은 시간이 소요된다. 예를 들어 항상 0번째 요소를 반환하는 함수라고 하면, input에 100개의 숫자가 있는 리스트를 넣으나, 100000개의 숫자가 있는 리스트를 넣으나 같은 숫자가 걸리고 연산이 따로 필요 없다.
2) Logarithmic Time — O(log n)
크기가 n인 input data가 주어졌을 때, 문제를 해결하는 각 단계를 지날 때 마다 사이즈가 줄어드는 경우를 말한다. 이 경우에 항상 모든 value를 거칠 필요는 없다. range(0,10)이어도 되고, range(0,10,2)로 하나씩 건너뛰어도 같은 전체적으로 같은 시간이 걸린다고 취급한다는 말이다. 주로 이진트리나 이진검색에서 사용된다.
3) Linear Time — O(n)
input 데이터 수의 증가와 비례하여 복잡도 시간도 증가하는 경우를 말한다. 모든 value의 값을 살펴봐야 한다.
4) Quadratic Time — O(n²)
주로 중첩 반복문에 사용된다. 이름에서 알 수 있듯이 quadratic(2차의) 번 반복하며 리스트의 모든 value를 거쳐야 한다.
5) Exponential Time — O(c^n)
input data가 늘어날 때 복잡도 시간이 배가 되는 경우이다. 문제를 해결하기 위한 단계의 수가 상수값 c의 n제곱이 된다. 보통 메모이제이션을 사용하지 않는 재귀에 많이 쓰인다. 대표적인 예로는 피보나치 수열이 있다.
