분할 상환 분석
분할 상환 분석은 최악의 경우 일련의 연산에 대한 연산당 평균 비용의 상한을 설정하여, 가끔 발생하는 고비용 연산이 많은 저비용 연산에 걸쳐 비용이 분산될 때 저렴해질 수 있음을 보여줍니다.
Definition
분할 상환 분석은 자료 구조에 대한 일련의 연산 총 비용의 상한을 설정하고 연산 수로 나누어, 개별 연산 비용이 크게 다를지라도 전체 시퀀스에 걸쳐 최악의 경우에도 유지되는 연산당 분할 상환 비용을 산출하는 방법입니다.
Scope
이 주제는 분할 상환 분석의 세 가지 표준 기법인 총계법, 회계법(은행가법), 잠재력법과 동적 배열, 이진 카운터, 스플레이 트리, 서로소 집합(union-find) 구조와 같이 개별 연산 비용이 다양한 자료 구조에 대한 적용을 다룹니다. 또한 분할 상환 비용을 평균 사례 비용 및 연산당 최악 사례 비용과 구별합니다.
Core questions
- 분할 상환 비용은 연산당 최악 사례 비용 및 평균 사례 비용과 어떻게 다른가요?
- 총계법은 연산 시퀀스의 총 비용 상한을 어떻게 설정하나요?
- 회계법은 나중에 발생하는 고비용 연산을 지불하기 위해 크레딧을 어떻게 할당하나요?
- 잠재력법은 비용을 평활화하기 위해 잠재력 함수를 어떻게 사용하나요?
- 어떤 자료 구조가 연산당 경계보다는 분할 상환 보장에 의존하나요?
Key concepts
- 분할 상환 비용
- 총계법
- 회계법(은행가법)
- 잠재력법
- 잠재력 함수
- 동적 배열 두 배 확장
- 이진 카운터 증가
- 경로 압축을 사용한 유니온-파인드
Key theories
- 잠재력법
- 잠재력법은 자료 구조의 상태에 비음의 잠재력을 할당합니다. 연산의 분할 상환 비용은 실제 비용에 잠재력 변화를 더한 값으로, 저비용 연산은 나중에 발생하는 고비용 연산을 지불할 잠재력을 축적합니다.
- 회계법(은행가법)
- 회계법은 일부 연산에 실제 비용보다 더 많은 비용을 부과하고, 잉여분을 자료 구조 요소에 크레딧으로 저장하여 미래의 고비용 연산을 지불하며, 크레딧이 음수가 되지 않도록 보장합니다.
Clinical relevance
분할 상환 분석은 동적 배열(크기 조정 가능한 리스트), 재해싱하는 해시 테이블, 연결성 및 최소 신장 트리 알고리즘에 사용되는 유니온-파인드, 스플레이 트리와 같은 자체 조정 구조 등 많은 널리 사용되는 구조가 가끔 발생하는 고비용 연산에도 불구하고 실제로 효율적인 이유를 설명합니다. 이들은 모두 연산당 보장보다는 분할 상환 보장에 의존합니다.
History
분할 상환 분석이라는 용어와 체계적인 프레임워크는 1985년 로버트 타잔(Robert Tarjan)에 의해 도입되었으며, 이전의 임시적인 논증들을 기반으로 합니다. 이 기법은 1980년대 타잔과 슬레이터(Sleator)가 개발한 자체 조정 자료 구조(스플레이 트리, 피보나치 힙)를 분석하는 데 핵심적이었습니다.
Key figures
- Robert Tarjan
- Daniel Sleator
Related topics
Seminal works
- tarjan1985amortized
- cormen2009
Frequently asked questions
- 분할 상환 비용은 평균 사례 비용과 동일한가요?
- 아닙니다. 평균 사례 비용은 입력의 확률 분포에 대한 기댓값이며, 불운한 입력에 의해 위반될 수 있습니다. 분할 상환 비용은 무작위성이 가정되지 않은 일련의 연산에 대한 최악의 경우 보장입니다. 이러한 시퀀스의 총 비용은 제한되므로 연산당 평균은 항상 유지됩니다.
- 동적 배열에 추가하는 것이 크기 조정이 O(n)일 때 왜 분할 상환 O(1)인가요?
- 배열은 일반적으로 용량을 두 배로 늘리기 때문에 크기 조정은 추가에 비해 드물게 발생하며, n번의 추가 시퀀스에 걸친 총 복사 작업은 n에 비례합니다. 모든 추가에 걸쳐 분산되면 단일 크기 조정이 선형일지라도 일정한 분할 상환 비용을 제공합니다.