https://kyopro-friends.hatenablog.com/entry/2025/02/18/195030

サーバルだよ！
マシュマロでもらった償却計算量についての質問で、私が間違ったことを言っちゃったみたいだから、ちゃんと調べ直して記事にしたよ。

サーバル「償却計算量っていうのはある意味での"平均"を考えてえるってことだから、「最悪O(1)」の操作なら「償却O(1)」っていう必要はないよ。言っても別に間違いじゃないけどね」#マシュマロを投げ合おう https://t.co/hLsAGBx6eI pic.twitter.com/LclKpCP65f
— 競技プログラミングをするフレンズ (@kyopro_friends) 2025年2月14日

償却計算量の定義

ガイドさんにも調べてもらったけど、償却計算量のちゃんとした定義はよくわかんなかったよ……。もし、一般的な定義があったら教えてね。
この記事ではnoshiさんの定義を使うことにするよ。

noshi91.hatenablog.com

データ構造に対して、起こり得る操作全体を $M$ とする。操作の償却計算量が $(A_m)_{m∈M}$ であるとは、任意の操作列 $(m_i)_{i=1}^n$ に対して
$操作列 (m_i)_{i=1}^n を実行する実際の計算量 \leq \sum_{i=1}^{n}A_{m_i}$
が成り立つことと定義する。ここで、操作列 $(m_i)_{i=1}^m$ は「何もない」状態から始まるもののみを指す。つまり、最初の操作 $m_1$ は「空の heap を作る」や「与えられた列から、segment tree を構築する」などになる。 (この条件が無いと、重い操作 1 つからなる列の計算量が壊れてしまう)

この定義からわかる通り、償却計算量の取り方は一意じゃないね。つまり操作1,2の2種類の操作を持つデータ構造に対して

償却計算量で、操作1は $O(1)$ 時間、操作2は $O(N)$ 時間
償却計算量で、操作1は $O(N)$ 時間、操作2は $O(1)$ 時間

の2つの主張がどちらも償却計算量の定義にあうことがあり得るよ！

償却計算量を求めるテクニックはいろいろあるみたいだけど、ここでは、各操作の計算量を直接考えてその収支をみる Banker's method と、ポテンシャル関数を使う Physicist's method を紹介するよ。

Banker's method

Banker's method は、償却計算量の定義を直接確かめる手法だよ。
「各操作で償却計算量に相当する分だけお金が貰えるので、そのお金を使ってデータ構造に対する操作を行い、途中で破産しないことを示す」っていう気持ちのものだね。

例として、元の質問にあった lazy binomial heap で push と pop だけを持つデータ構造の償却計算量を Banker's method で考えてみるよ。
「pushするときに $2$ 円貰える。popするときには heap 内の要素数を N として $1+2\log N$ 円貰える。計算機を動かすには1ステップあたり $1$ 円かかる」とすると、操作の途中で破産することがないことが証明できるから、「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」といえるね。（証明はさっきのリンク先を見てね）

Physicist's method

Physicist's methodは、"ポテンシャル関数"っていう関数を導入して、その関数の値の変化を観察することで償却計算量を考える手法だよ。
ポテンシャル関数っていうのは、データ構造の状態から0以上の数への関数で、Banker's method の"貯金額"にあたるものを表す気持ちのものだよ。
ポテンシャル関数を使うと何が嬉しいかっていうと、Banker's method だと「操作列に対して、破産しないか」を考えていたところを、Physicist's method だと「操作によるデータ構造の状態変化に対して、ポテンシャル関数の変分が実計算量に見合うか」だけを考えれば良くなって、ポテンシャル関数さえうまく決められれば、あとの証明は簡単になるになるところだね！
Banker's method と同じように操作での収支を考えると
$(操作前のポテンシャル関数の値)+(操作の償却計算量)-(操作の実計算量)=(操作後のポテンシャル関数の値)$
になるから、変形するとこう！
$(操作の償却計算量)=(操作の実計算量)+( (操作後のポテンシャル関数の値)-(操作前のポテンシャル関数の値))$
lazy binomial heap の例だと、tree の個数をポテンシャル関数の値とすると「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」が言えるよ。

変な償却計算量

lazy binomial heap の push はリストの最後に要素を追加するだけだから最悪 $O(1)$ 時間だね。popは運が良ければ $\Theta(1)$ 時間で済むけど、最悪のときは heap 内の要素数を N として $\Theta(N)$ 時間かかるね（要素数 1 の木が N 個あるとき）。最良/最悪計算量は、操作の実際の計算時間だけで決まるもので、償却計算量とは全然別物だよ。
ところでさっき、①「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」になるっていったよね。実は、Banker's method で「push するときに $1+2\log(N+1)$ 円貰える。pop するときには $2$ 円貰える。計算機を動かすには1ステップあたり $1$ 円かかる」としても破産しないことが元と同じように示せるから②「償却計算量で、pushは $O(\log N)$ 、popは $O(1)$ 」も正しいといえるよ！

ただ、そもそも償却計算量って「データ構造の状態次第で計算量が変わる操作に対して"平均的な"処理速度を考えたい」って気持ちで考えてることが多いから、「データ構造の状態によらずに最悪 $O(f)$ 時間の操作」の償却計算量は $O(f)$ になるように、操作に対する償却計算時間の組を決めるのが自然だね。
①を使って「pushは最悪 $O(1)$ 、popは償却 $O(\log N)$ 」って言うのは誤解を招くことはほとんどないはずだけど、②が言えるからって「pushは最悪 $O(1)$ 、popは償却 $O(1)$ 」って言うのはかな～～りミスリードだと思うよ。

質問に対する答え

「全ての計算量が償却計算量になるか？」に対する答えは、「ポテンシャル関数の値に影響するものはそう。ただし、償却計算量と最悪計算量が一致してるなら、その2つの区別をつけなくても困ることはないはず」だよ！

謝辞

noshi91 さんにいろいろ教えてもらったよ。ありがと～