알고리즘의 점근 적 분석은 런타임 성능의 수학적 경계 / 프레임을 정의하는 것을 말합니다. 점근 분석을 사용하면 알고리즘의 최상의 경우, 평균 사례 및 최악의 시나리오를 매우 잘 결론을 내릴 수 있습니다.

점근 분석은 입력 바운드입니다. 즉, 알고리즘에 대한 입력이 없으면 일정한 시간에 작동하는 것으로 결론을 내립니다. "입력"이외의 다른 모든 요소는 상수로 간주됩니다.

점근 분석은 수학적 계산 단위로 연산의 실행 시간을 계산하는 것을 말합니다. 예를 들어, 한 작업의 실행 시간은 f (n)로 계산되고 다른 작업의 경우 g (n 2 ) 로 계산 될 수 있습니다 . 즉, 첫 번째 작업 실행 시간은 n 이 증가함에 따라 선형 적으로 증가 하고 두 번째 작업의 실행 시간은 n 이 증가하면 기하급수적으로 증가합니다. 마찬가지로 n 이 상당히 작으면 두 작업의 실행 시간이 거의 동일합니다 .

일반적으로 알고리즘에 필요한 시간은 세 가지 유형에 속합니다.

• 모범 사례 -프로그램 실행에 필요한 최소 시간.
• Average Case- 프로그램 실행에 필요한 평균 시간.
• 최악의 경우 -프로그램 실행에 필요한 최대 시간.

점근 표기법

다음은 알고리즘의 실행 시간 복잡도를 계산하기 위해 일반적으로 사용되는 점근 표기법입니다.

• Ο 표기법
• Ω 표기법
• θ 표기법

Big Oh 표기법, Ο

표기법 Ο (n)은 알고리즘 실행 시간의 상한을 표현하는 공식적인 방법입니다. 최악의 시간 복잡도 또는 알고리즘이 완료하는 데 걸릴 수있는 가장 긴 시간을 측정합니다.

예를 들어 함수 f (n)의 경우

Ο(f(n)) = {g(n) : there exists c > 0 and n0 such thatf(n) ≤ c.g(n) for all n > n0. }

오메가 표기법, Ω

표기법 Ω (n)은 알고리즘 실행 시간의 하한을 표현하는 공식적인 방법입니다. 최적의 시간 복잡도 또는 알고리즘이 완료하는 데 걸릴 수있는 최적의 시간을 측정합니다.