데이터 구조의 상각 시간 복잡성

상각 분석

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

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

집계 방법

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

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

$\frac{비용( n\:작업)}{n}=\frac{비용(일반\:작업)+비용(비싼\:작업)}{n}$

상각 분석의 예

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

동적 배열의 경우 ci =i번째 삽입 비용입니다.

$So\:ci=1+\begin{케이스}i\:-\:1,if\:i-1\:is\:power\:of\:2 \\0, \:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:그렇지 않으면 \end{cases}$

$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{ \l그룹 n-1\r그룹}\rfloor} 2j}{n}=\frac{O\l그룹 n\r그룹}{n}$$