상각 분석

상각 상각 분석

이 분석은 간헐적 작업이 매우 느리지만 매우 자주 실행되는 대부분의 작업이 더 빠를 때 사용됩니다. 해시 테이블, 디스조인트 세트 등에 대한 분할상환 분석이 필요한 데이터 구조

Hash-table에서 탐색 시간 복잡도는 대부분 O(1)이지만 가끔 O(n) 연산을 수행하기도 한다. 대부분의 경우 해시 테이블에서 요소를 검색하거나 삽입하려는 경우 작업을 수행하는 데 일정한 시간이 소요되지만 충돌이 발생하면 충돌 해결을 위해 O(n)배 작업이 필요합니다.

집계 방법

집계 방법은 총 비용을 찾는 데 사용됩니다. 많은 데이터를 추가하려면 이 공식으로 상각 비용을 찾아야 합니다.

일련의 n 작업에 대해 비용은 -

상각 분석의 예

동적 배열의 경우 O(1) 시간에 주어진 인덱스에 항목을 삽입할 수 있습니다. 그러나 해당 인덱스가 배열에 없으면 일정한 시간에 작업을 수행하지 못합니다. 이 경우 처음에는 배열의 크기를 두 배로 한 다음 인덱스가 있으면 요소를 삽입합니다.

동적 배열의 경우 let =ith의 비용 삽입.