점근적 분석

점근적 분석

점근적 분석을 사용하여 입력 크기를 기반으로 하는 알고리즘의 성능에 대한 아이디어를 얻을 수 있습니다. 정확한 실행 시간을 계산해서는 안되지만 실행 시간과 입력 크기 간의 관계를 찾아야 합니다. 입력의 크기가 증가할 때 실행 시간을 따라야 합니다.

공간 복잡도의 경우, 우리의 목표는 알고리즘을 완료하기 위해 메인 메모리에서 얼마나 많은 공간이 점유되는지에 대한 관계 또는 함수를 얻는 것입니다.

점근적 행동

f(n) 함수의 경우 점근적 동작은 n이 커질수록 f(n)이 증가하는 것입니다. 작은 입력 값은 고려되지 않습니다. 우리의 임무는 입력의 큰 값에 대해 얼마나 많은 시간이 걸릴지 찾는 것입니다.

예를 들어, f(n) =c * n + k는 선형 시간 복잡도입니다. f(n) =c *(n*n) + k는 2차 시간 복잡도입니다.

알고리즘 분석은 세 가지 다른 경우로 나눌 수 있습니다. 경우는 다음과 같습니다

최상의 사례 − 여기에서 실행 시간의 하한이 계산됩니다. 최적의 조건에서 알고리즘의 동작을 설명합니다.

보통 사례 − 이 경우 알고리즘 실행 시간의 상한과 하한 사이의 영역을 계산합니다. 이 경우 실행되는 작업의 수는 최소가 아니고 최대가 아닙니다.

최악의 경우 − 이 경우 알고리즘 실행 시간의 상한을 계산합니다. 이 경우 최대 연산 횟수입니다.