ならし計算量のよくある誤解について

ならし計算量 (amortized complexity) というのがありますが、競プロ初心者層には誤解されがちな概念なので、誤解を解くためのことを書きたくなりました。

以下で「よくある誤解」と称して架空の人物がしゃべりますが、複数回見てきた事例であり、特定個人に対する揶揄等ではありません。えびちゃん自身の事例である場合もあります*1。

多少知っている人へ：ポテンシャル解析などの話を直接はしないので、そういうのは別の記事を見に行ってほしいです。文献の紹介くらいはあります。

å°Žå…¥

データ構造の計算量などで、次のような記述を見かけることがよくあります。

• vector へのアクセス a[i] は、最悪 \(O(1)\) 時間
• set での二分探索 a.lower_bound(x) は、最悪 \(O(\log(n))\) 時間

これらは、「一番悪いときでも \(O(1)\) 時間や \(O(\log(n))\) 時間だから安心だな〜」という気持ちで読める人が多そうです。

一方で、次のような記述もよくあります。

• vector の末尾への追加 a.push_back(x) は、ならし \(O(1)\) 時間
  • 償却 \(O(1)\) 時間という言い方もあり、これらは同じ意味
  • 同様に、ならし計算量を償却計算量とも言う
• union_find での操作 a.unite(i, j) ã‚„ a.find(i) は、ならし \(O(\alpha(n))\) 時間

これらは、誤解して「ならしってなに？ やばいときは \(O(1)\) 時間や \(O(\alpha(n))\) 時間にならなくて、知らないうちに TLE になったりしそう？で不安だな〜」という気持ちになる初心者が多い印象があります。

実際には、少なくとも競プロ文脈で言えば、「ならしで \(O(1)\) 時間や \(O(\alpha(n))\) 時間だから安心だな〜」となれるくらいのうれしい保証なので、その説明をします。

説明

お気持ち

データ構造に対して \(n\) 回操作し、\(n\) 回の合計の計算量が \(f(n)\) であったとき、一回あたりの計算量は \(f(n)/n\) と見なせます。 そこで、実際の操作一回一回の計算量は考えず、この \(f(n)/n\) について考えてみることにします。

たとえば \(f(n) = O(n)\) であれば、一回あたり \(O(1)\) 時間ということになります。

これをもう少しちゃんと保証したものが、ならし計算量と呼ばれるものです。

定義（ゆるふわ）

あるデータ構造に対して行える操作（vector に対する push_back とか、stack に対する push・pop とか）を考えます。それらをどういう順番で \(n\) 回処理した場合でも、合計が \(f(n)\) 時間以下になるとします。このとき、それらの操作は「ならし \(O(f(n)/n)\) 時間」であると言います。

たとえば、「union_find に対する操作はならし \(O(\alpha(n))\) 時間」というのは、「union_find に対して \(n\) 回操作をすると \(O(n\cdot \alpha(n))\) 時間」のような意味合いです。

定義（かっちりめ）

データ構造に対する任意の操作列 \( (op_1, op_2, \dots, op_n)\) を考えます（\(op_1\) が .push_back(x) とか、そういう感じです）。 このとき、\(op_i\) (\(1\le i\le n\)) に対して、実際の計算量を \(t(op_i)\) とします。 さらに、\(a(op_i)\) が存在して、各 \(1\le k\le n\) に対して以下が成り立つとします。 \[ \sum_{i=1}^k t(op_i) \le \sum_{i=1}^k a(op_i). \] このとき、\(a(op_i)\) を（\(op_i\) の）ならし計算量と呼びます。

\(t(op_i) \le a(op_i)\) (\(1\le i\le n\)) が成り立つ必要はなく、\(i\) 回目以前の操作の合計さえ抑えられればよいのがミソです。

\(n\) 回の操作全体の計算量が \(\sum_{i=1}^n a(op_i)\) で抑えられるため、たとえば \(op_i\) が「ならし \(O(\log(n))\) 時間」と保証されている操作であれば、全体で \(O(n\log(n))\) 時間とわかったりするわけです。

（補足） この \(a(op_i)\) をうまいこと求めるのが、各問題でならし計算量を求めるために必要なことであり、ならし解析 (amortized analysis) などと呼ばれているものです。解析の具体例だけを見せられると天才に見えますが、典型的な手法がいくつかあります。

やや細かい話

実際には、\(n\) が「操作列の長さ」なのか「その時点のデータ構造のサイズ」なのか「それ以前のデータ構造のサイズの最大値」なのかがぼかして話されたりしがちな気もします。

「空の状態から始めて、操作ごとに増える要素の個数が高々 1 つ」であるような場合には、データ構造のサイズが操作列の長さで上から抑えられるので、問題なさそうな気もします。

そうでない場合は少し気にする必要があるかもしれません。 「サイズ \(n\) で初期化して \(m\) 回操作する」ような場合には、初期化の計算量 \(t(op_0)\) も合わせて考えるかもしれません。 あんまり初期化のことを書いている文献はないかもしれません。

\(\Theta\) とか \(\Omega\) とかの話

ならし計算量の定義だと上からしか抑えてないけど、ならしで \(\Theta\) や \(\Omega\) ってうまく定義されてる？

「ある操作列が存在して」か「任意の操作列に対して」かは文脈にもよりそうだけど、下から抑えれば定義できる？ できそう。

\(O\) 以外を知らない人向け → やや長めの記事

よくある例

可変長配列

vector の .push_back のようなものです。ざっくり以下のようなアルゴリズムです。

• 初め、長さ \(1\) の領域を確保する
• 確保した領域に新しく要素を置けるなら置く（\(O(1)\) 時間）
• 確保した領域が足りなくなったら、長さを倍にしてから置く（領域の長さを \(k\) として \(\Theta(k)\) 時間）

長さ \(n\) にするための計算量は？となり、「\(\Theta(n)\) 時間の操作があって \(n\) 回だから \(\Theta(n^2)\) 時間か...？」とか「\(\Theta(n)\) 時間の操作は \(\floor{\log_2(n)}\) 回起きるから \(\Theta(n\log(n))\) 時間か...？ \(\log\) は定数（）だから一回あたり \(O(1)\) 時間と言われているだけなのか...？」となったりしますが、そうではないです。

長さ \(k\) は毎回固定ではなく \(1 + 2 + 4 + \dots + 2^{\floor{\log_2(n)}}\) のようになっているため、（等比数列の和であることに注意するなどして）全体で \(\Theta(n)\) 時間であることがわかります。

キュー

二つのスタックでキューを作ることができ、two-stack queue などと呼ばれます*2。

下の方にあるスライドにも載っているので、詳細は割愛します。似た方法で deque も作れます*3。

カウンタ

\(0\) から始めて \(n\) まで \(1\) ずつ増やすことを考えます。このとき、各インクリメントに対して、数字が変化する桁はならし \(O(1)\) 個であることが示せます。 なので、変わった桁のみをうまく管理することで、たとえば以下のようなクエリをならし \(O(1)\) 時間で処理できます。

• 値を \(1\) 増やす
• 桁和を出力する
  • あるいは桁の二乗和とかを出力する

ゆるふわな話

ならしのイメージの話です。

たとえば、「1 日に使った金額が 100 円を超えちゃいけませんよ」と「1 週間に使った金額が 700 円を超えちゃいけませんよ」という制限を考えます。 後者は「平日は 1 円も使わずに土日に 350 円ずつ使う」といった行動が許されるのに対し、前者ではそうしたことが許されません。

この前者が最悪計算量（各クエリの実際の計算量）に相当し、後者がならし計算量（全体で見たときに一回あたりと見なせる計算量）に相当するつもりです。

より実態に即しているイメージをフォロヮにもらったので書きます。前者は「毎日 100 円ずつあげるけど、使わなかったぶんは没収ね」で、後者は「毎日 100 円ずつあげるから、使っても貯金してもいいよ（借金はだめ、利子はなし）」です。計算量が小さい操作をしたのが貯金を作ったことに相当します。

ならしがうれしい話

ならし計算量が解析の面でうれしい状況としては、

• 一回一回の解析は難しいが、全体で見れば解析が簡単
• 重いクエリもあるが、全体で見れば十分軽い

のようなものがあります。それはそれとして、「全体としての計算量さえ保証すればいいときは、ならしだけ保証するように設計する」という方針がうれしいケースもあります。

たとえば、\(n\) 個の操作の計算量が \( (1, 1, \dots, 1, n)\) で合計 \(2n-1\) になっているデータ構造があったとします。 これはならし \(O(1)\) 時間ですが、最悪 \(O(1)\) 時間ではありません（最後の一回が \(n\) になっているので）。

これをなんとか工夫することで \( (10, 10, \dots, 10, 10)\) にできたとします。これは最悪 \(O(1)\) 時間を保証できていますが、合計としては \(10n\) に増えてしまっています。

このとき、定数倍が悪くなっている上、全体のオーダーが改善されているわけでもなく、実装の工夫も必要になってしまい、大変づくしです。

もちろん、最悪計算量を保証するために必ずしも定数倍がハチャメチャに悪化するわけではないので状況によりけりですが、ゆるい制限でいいならそれに応じてうまくやりましょうということです。

ならしだと困る話

競プロだとあんまりないと思います。

たとえば、Web サイトなどで「\(i\) 番目のアクセスに対しては、データ構造に対して処理 \(i\) を行う」という処理があったとします。 このとき、ならし計算量しか保証されていないと、一部のユーザが「めちゃくちゃ時間かかった」というような体験をすることになり、あまりうれしくなさそうです。

競プロでも困る例をフォロヮにもらったので書きます。 「ならし○○時間」の操作を普通にするだけなら問題ないと思いますが、rollback が可能なデータ構造に書き換えようとするときに、元が「ならし」のデータ構造だとつらいことがあります。

先のカウンタの例で言えば、999...9 から（大きい計算量で）1000...0 に更新したあと、rollback をして（大きい計算量で）999...9 に戻り、また（大きい計算量で）1000...0 に更新して、... というのを繰り返すと、毎回大きい計算量がかかるようになりますね。

とはいえ、「ならし○○時間」と保証されているデータ構造を、保証されている通りに使えば問題ないことには変わりない気はします。

ならし計算量あるあるデータ構造

C++/STL にもいろいろありますね。

• vector の .push_back(x) はならし \(O(1)\) 時間
  • このせいで、vector を内部で使うデータ構造は大抵ならしになりがち
• set の .erase(it) はならし \(O(1)\) 時間
  • コストを .insert(x) に押しつけることで、.erase(it) の方はならせそう？
  • それはそれとして、赤黒木を平衡させる操作はならし \(O(1)\) 時間
    • どこに挿入・削除するかは、ポインタなどを持っていないと \(O(1)\) で決められないことに注意
    • it はイテレータ

STL ではないものの競プロでよくあるデータ構造にもいろいろあります。

• union_find の .unite(i, j) ã‚„ .find(i) は（適切に実装すれば）ならし \(O(\alpha(n))\) 時間
  • 実際には、サイズ \(n\) のそれに \(m\) 回操作すると \(\Theta(n+m\,\alpha(m, n))\) 時間で、\(O(\alpha(n))\) 時間よりも厳しく抑えられる
  • \(\alpha(m, n)\) については → そういう記事
• foldable_queue の .fold() ã‚„ .push(x) はならし \(O(1)\) 時間
  • いわゆる SWAG（を勝手にそう呼んでいます）
    • queue への push/pop と、全体のモノイド積 (fold) を処理するデータ構造
    • push と fold は最悪 \(O(1)\) 時間
  • two-stack queue を応用して実装する（ので deque でも可能）
• decremental_neighbor_query の .less_than(i) ã‚„ .greater_equal(i) などは、ならし \(O(1)\) 時間
  • \(\{1, 2, \dots, n\}\) で初期化した集合に対し、削除操作と、隣の要素の検索ができる
• skew_heap の .meld(q) はならし \(O(\log(n))\) 時間
  • ヒープ（優先度つきキュー）二つに対して、それらをくっつけて一つのヒープにする操作を meld と呼ぶ
• fibonacci_heap の .prioritize(it, k) はならし \(O(1)\) 時間
  • ヒープに対して、ある要素の優先度を高める操作（取り出されやすくする）を prioritize と勝手に呼んでいます
    • 文献によっては decrease_key とか言うかも
  • この操作を \(O(1)\) 時間でできることにより、Dijkstra 法の計算量を \(O(|E|\log(|V|))\) から \(O(|E|+|V|\log(|V|))\) に改善できる

まとめ

ならし計算量は、操作列を全体として見たときの計算量を保証してくれるため、競プロ文脈では「最悪○○時間」と同程度にえらい保証と見なしてよいです。 「入力によっては○○時間になってくれず TLE（平均計算量）」とか「乱数の値によっては○○時間になってくれず TLE（期待計算量）」とかとは事情が異なります。

参考文献

• cs166.1266
  • 図とかがたのしい感じの講義スライド
  • 他にもいろいろなトピックがある
• 熨斗袋の記事
  • ならし以外にも、期待計算量や平均計算量についても載っている

おわり

にゃんこ。

*1:そういう意味では特定個人ですが、自分なので許されます。

*2:文法としては、two-week vacation とかのように、ハイフンで数詞とつないで名詞が単数形になる形容詞のやつです。two-stacks queue や two-stack-queue ではないです。

*3:概要：片方が空になったときに \(k\) 個移すのではなく \(\ceil{k/2}\) 個移します。