왜 우리는 피보나치 힙에 대한 상각 된 분석을합니까?

Question

모든 작업 분석을위한 피보나치 힙은 본질 상 상각됩니다. 왜 우리는 이항 힙 (Binomial Heap)의 경우처럼 정상적인 분석을 할 수 없습니다.

Answer 1

이항 힙에서는 각 작업이 특정 최악의 성능으로 실행되도록 보장됩니다. 삽입은 O (log n) 이상의 시간이 걸리지 않으며 병합에는 O (log n + log m) 시간 이상 걸리지 않습니다. 따라서 이항 힙의 효율성을 분석 할 때 더 많은 것을 사용하는 것이 일반적입니다 전통적인 알고리즘 분석.

이제는 상환 분석을 할 때만 분명 해지는 이항 힙의 몇 가지 속성이 있습니다. 예를 들어, 힙이 초기에 비어 있다고 가정 할 때 이항 힙에 n 개의 연속 삽입을 수행하는 데 필요한 비용은 얼마입니까? 이 경우, 상각 된 상환 비용은 O (1)이며, 즉 n 번의 삽입 비용은 O (n)임을 알 수 있습니다. 이러한 의미에서 기존 분석을 바탕으로 상각 된 분석을 사용하면 처음에는보다 보수적 인 최악의 경우 분석에서 발생하는 것보다 데이터 구조에 대한 통찰력이 더 많이 나타납니다.

어떤 의미에서 피보나치 힙은 상각 된 의미로 가장 잘 분석됩니다. 왜냐하면 많은 작업에서 최악의 경우 경계가 실제로 그렇게 크지는 않지만 (예를 들어 삭제 분 또는 감소 키를 취할 수 있기 때문입니다 시간이 Θ (최악의 경우)), 모든 일련의 작업에서 피보나치 힙이 우수한 상각 성능을 나타냅니다. 개별 delete-min이 Θ (n) 시간이 걸릴 수도 있지만 일련의 m delete-mins가 Θ (m log n) 시간 이상 걸릴 수는 없습니다.

그러나 피보나치 힙은 최악의 경우가 아니라 상각 된 의미에서 효율적으로 설계되었습니다. 처음에는 Dijkstra와 Prim의 알고리즘 속도를 높이기 위해 발명되었습니다. n 노드 힙에서 m 감소 키와 n 삭제를 수행하는 데 드는 모든 비용이 중요합니다. 설계 목표이므로 설계자는 최악의 경우 피보나치 힙을 효율적으로 만듭니다.