Amortized Analysis
償却解析は一連の操作の総コストを各操作に平均化した上界を評価し、単一操作が時折高価であっても対応する。
目的
データ構造の操作シーケンス上の平均性能を解析し、動的配列拡張等に適用する。
メカニズム
三つの手法：集計解析（総コスト/操作数）、会計手法（安価操作に多く計上して高価操作を補填）、ポテンシャル手法（ポテンシャル関数 Φ で状態複雑度を測る）。動的配列挿入は償却 O(1)。
ユースケース
- データ構造の解析
- パフォーマンス保証
- アルゴリズム設計
償却解析は一連の操作の総コストを各操作に平均化した上界を評価し、単一操作が時折高価であっても対応する。
データ構造の操作シーケンス上の平均性能を解析し、動的配列拡張等に適用する。
三つの手法：集計解析（総コスト/操作数）、会計手法（安価操作に多く計上して高価操作を補填）、ポテンシャル手法（ポテンシャル関数 Φ で状態複雑度を測る）。動的配列挿入は償却 O(1)。