Asymptotic notation 알고리즘의 수행 시간을 표기하기 위해, 필수적인 부분에 집중하고 불필요한 상세들을 무시한다. 예를 들어, f(n) = n^2 + 2n 일 때, 시간 복잡도는 n^2이라고 한다. n이 무한대로 가는 데에선 낮은 차수의 증가폭이 높은 차수의 증가폭을 넘지 못하기 때문이다. 점근법 표기법 상한 표기법 : Big- O 점근적 상한만 알고 있을 때 사용하며 기껏해야 f(n)의 비율로 증가하는 함수 e.g. 7n-2가 O(n)임을 증명하라. sol) Let. c>0 이고 n_0 >= 1 n = 7n-2를 만족하는 c, n_0가 존재하는가? -> c=7,n_0 = 1일때 존재한다. 하한 표기법 : Big - Omega 점근적 하한만 알고 있을 때 사용하며 적어도 f(n)의 비..
