다이너마이즈

컴퓨터 과학에서, 동적화는 정적 데이터 구조를 동적 데이터 구조로 변환하는 과정이다.정적 데이터 구조는 매우 우수한 기능과 빠른 쿼리를 제공할 수 있지만, 그 효용은 빠르게 증가/축소할 수 없기 때문에 제한적이므로 입력 데이터의 양이 변화하는 동적 문제 해결에는 적용할 수 없다.동적화 기법은 동적 데이터 구조를 만드는 균일한 방법을 제공한다.

분해 가능한 검색 문제

We define problem ${\displaystyle P}$ of searching for the predicate ${\displaystyle M}$ match in the set ${\displaystyle S}$ as ${\displaystyle P(M,S)}$. Problem ${\displaystyle P}$ is decomposable if the set ${\displaystyle S}$ can be decomposed into subsets ${\displaystyle S_$${i}}$ and there exists an operation ${\displaystyle +}$ of result unification such that ${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$.

분해

분해는 컴퓨터 공학에서 정적 데이터 구조를 크기가 같지 않은 더 작은 단위로 쪼개기 위해 사용되는 용어다.기본 원리는 어떤 소수라도 다른 어떤 기초에서 표현으로 번역될 수 있다는 생각이다.항목에 대한 자세한 내용은 분해(컴퓨터 과학)를 참조하십시오.단순성을 위해 이 글에서는 바이너리 시스템을 사용하지만 다른 베이스(피보나치 수 등 다른 가능성)도 활용할 수 있다.

바이너리 시스템을 사용하는 경우 $n{\displaystyle }$ ${\displaystyle n}$ 요소의$$ 세트가 다음 크기의 하위 집합으로 분할됨

${\displaystyle 2^{i}*n_{i}}$

여기서 ${\displaystyle n_{}}${\$displaystyle n_{i}$은(는) $이진수$인 n ${\$$displaystyle$ i$}$의 i ${\$$displaystyle n}$번째$$ 비트다.즉, $n{\displaystyle }$ ${\displaystyle n}$에 $i{\displaystyle }$ ${\displaystyle i}$ -th$$ 비트가 0인 경우 해당 집합에 요소가 포함되지 않는다.각각의 서브셋은 원래의 정적 데이터 구조와 동일한 속성을 가진다.새로운 동적 데이터 구조에서 수행되는 작업에는 분해에 의해 형성된 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$(${\displaystyle n}$ ${\displaystyle )}$ ${\$ 세트의$$ 통과가 포함될 수 있다.따라서 정적 데이터 구조 작업과 반대로 $O{\displaystyle (\log }$ ${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$) ${\displaystyle O(\log \left(n\wright))}$ 요소를$$ 추가하지만 삽입/삭제 작업이 추가될 수 있다.

커트 멜혼은 이 아이디어에 따라 역동화된 데이터 구조에서 운영의 시간 복잡성에 대한 몇 가지 방정식을 증명했다.이러한 동등성 중 몇 가지가 열거되어 있다.

만약

${\displaystyle P_{S}\left(n\right)\,\!}$ = time to build the static data structure ${\displaystyle Q_{S}\left(n\right)\,\!}$ = time to query the static data structure ${\displaystyle Q_{D}\left(n\right)\,\!}$ = time to query the dynamic data structure formed by decomposition $$$'{\$ $$= 상각된 삽입 시간

그때

 ${\displaystyle Q_{D}\왼쪽(n\오른쪽)=O(Q_{S}\좌(n\우)\log \좌(n\우)\,\!}$  ${\displaystyle {\overline{I}=O(\좌측(P_{S}\좌측(n\우측)/n\log \좌측(n\우측)}}$ 

$Q{\displaystyle {}_{}}$ ${\displaystyle S_{}}$( ${\displaystyle n}$) ${\$이(가) 적어도 다항식인 경우, $Q{\displaystyle {}_{}}$ ${\displaystyle D_{}}$(${\displaystyle }$n )${\displaystyle }$= O${\displaystyle }$( ${\displaystyle Q{}_{}}$ ${\displaystyle S_{}}$( ${\displaystyle n}$)${\$$O\왼쪽(Q_{S$}\왼쪽$(n\오른쪽)\오른쪽)}$.

추가 읽기

• 커트 멜혼, 데이터 구조와 알고리즘 3, . EATCS Series, vol. 3, Springer, 1984.