Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 정적 손가락 정리


정적 손가락 정리 − f를 finger라고 하는 특정 요소로 취급한다고 하자.

그런 다음 아래 표현식은 시퀀스 재생 비용에 대한 경계입니다.

O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j

참고 − |f-i| 손가락과 항목 i 사이의 항목의 대칭 순서의 거리로 표시됩니다.

여기서 m은 최대 n개의 노드가 있는 트리에 대한 업데이트 또는 액세스 작업의 수로 표시됩니다.

적어도 상각된 의미에서 n 노드를 초과하지 않는 트리에서 처음 m 작업에 걸리는 시간은 AVL 트리, 2-3 트리 등과 같은 균형 이진 탐색 트리에 걸리는 시간과 유사합니다.