[알고리즘] 점근표기법, asymptotic notation | 상한, 하한, 교집합
점근 표기법(asymptotic notation)은 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 교집합(Θ)이 있다. 먼저 간략하게 뜻을 말하면 아래와 같다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 하나 하나 알아보기전에, 앞서 말한 '빠르다', '느리다'라는 표현에 대해 그 뜻을 정리할 필요가 있다. 함수의 차수가 높을수록 더 빠를 것 같지만, 차수가 낮은 것이 더 빠르다고 표현한다. 즉, 그래프 상으로 그렸을 때 더 아..
