asymptotic (1) 썸네일형 리스트형 [Lecture 7] 점근(asymptotic) 표기법/ Big-O 표기법 #Big-O 표기법 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 대표적으로 다음의 세 가지 표기법이 있다. 대문자 O 표기법 알고리즘의 상한 및 상한은 필요한 시간의 가장 많은 양(최악의 경우 성능)으로 정의된다. 빅 오 표기법은 점근적 상한을 설명하는 데 사용된다. 수학적으로, 만약 f(n)가 알고리즘의 실행 시간을 설명한다면, f(n)는 O(g(n)이고, 양의 상수 C가 존재하고 n이 존재한다면, 모든 n >= n0에 대해 0 0과 N > 0이 존재한다면 f(n)는 Ω(g(n)이라고 말한다. Big-Ω는 n의 충분히 큰 값에 대해 함수의 성장률에 대한 하한을 나타낸다. #Bi.. 이전 1 다음