典型タグ

単調進行による償却解析

要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。

この典型を扱う単元: 単調進行による償却解析

検索別名: amortized analysis、light-edge size halving、potential method、償却解析、軽辺サイズ半減

未知問からこの典型を見つける手掛かり

扱う対象
  • 候補
  • 操作列
  • 要素
使う手掛かり
  • light edge
  • size halving
  • 一度だけ
  • 単調に減る
  • 移動回数
  • 部分問題サイズ半減
保つ不変量
  • potential
  • 総削除回数
  • 軽辺遷移ごとのサイズ半減
求めるもの
  • 償却上界
  • 総計算量
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: モデル変換

    関連する典型

      学習成果と学習単位

      • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

        単調進行による償却解析で学ぶ

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。