반응형 master method1 시간복잡도 정리 1. 점근표기법(Asymptotic Notation) 1) 빅 오 표기법(O(n)) 빅 오 표기법의 정의는 다음과 같다. 모든 N≥N₀에 대해 f(N)≤cg(N)이 성립하는 양의 상수 c와 N₀가 존재하면, f(N)=O(g(N))이다. 이때 g(N)이 f(N)의 상한이 된다. 예를 들어 f(N)= 4N²+N+1 이라는 식이 있을 때 2보다 큰 N에 대해서 g(N)=N², c=5라면 항상 f(N)≤cg(N)이 성립한다. 주의할 점은 g(N)을 찾을 때 가장 차수가 낮은 함수를 선택하는 것이다. 차수가 높은 함수를 선택하게 될 경우 시간복잡도를 과장해서 추정하게 되기 때문이다. 2) 빅 오메가 표기법(Ω(n)) 빅 오메가 표기법의 정의는 다음과 같다. 모든 N≥N₀에 대해 f(N)≥cg(N)이 성립하는 양의.. 2021. 9. 8. 이전 1 다음 반응형
