Python-상각 분석

상각 분석에는 입력 값의 데이터 분포 범위를 고려하지 않고 프로그램의 작업 순서에 대한 실행 시간을 추정하는 작업이 포함됩니다. 간단한 예는 정렬 된 목록에서 값을 찾는 것이 정렬되지 않은 목록에서보다 빠르다는 것입니다. 목록이 이미 정렬 된 경우 데이터가 얼마나 분산되어 있는지는 중요하지 않습니다. 그러나 물론 목록의 길이는 알고리즘이 최종 결과를 얻기 위해 거쳐야하는 단계 수를 결정하므로 영향을 미칩니다.

따라서 정렬 된 목록을 얻는 단일 단계의 초기 비용이 높으면 요소를 찾는 후속 단계의 비용이 상당히 낮아집니다. 따라서 상각 분석은 일련의 작업에 대한 최악의 실행 시간에 대한 한계를 찾는 데 도움이됩니다. 상각 분석에는 세 가지 접근 방식이 있습니다.

• Accounting Method− 여기에는 수행 된 각 작업에 비용을 할당하는 것이 포함됩니다. 실제 작업이 지정된 시간보다 빨리 완료되면 분석에 긍정적 인 크레딧이 누적됩니다. 반대 시나리오에서는 마이너스 크레딧이됩니다. 이러한 누적 크레딧을 추적하기 위해 스택 또는 트리 데이터 구조를 사용합니다. 목록 정렬과 같이 조기에 수행되는 작업은 상각 비용이 높지만 순차적으로 지연되는 작업은 누적 된 크레딧이 활용되므로 상각 비용이 낮습니다. 따라서 상각 된 비용은 실제 비용의 상한입니다.

• Potential Method−이 방법에서 저장된 크레딧은 데이터 구조 상태의 수학적 기능으로 향후 작업에 사용됩니다. 수학적 함수의 평가와 상각 된 비용은 동일해야합니다. 따라서 실제 비용이 상각 된 비용보다 클 경우 잠재력이 감소하고 비용이 많이 드는 향후 작업에 활용됩니다.

• Aggregate analysis −이 방법에서는 n 단계의 총 비용에 대한 상한을 추정합니다. 상각 된 비용은 총 비용과 단계 수 (n)의 단순 분할입니다.