計算量について、償却/期待/平均など

本記事は皆様からのご指摘を募集しております

誤った記述があるかもしれません

概要

競技プログラミングをやっていると ${\rm average} \ \mathrm{O} ( N )$ などの表記を見掛けることも多いでしょう *1。 ${\rm best} , {\rm worst} , {\rm average} , {\rm expected} , {\rm amortized}$ それぞれについて、大雑把な意味をまとめました。アルゴリズムの挙動の正確な把握は競技においても重要です。
以降、全て時間計算量に付いて議論します。

注: 本稿内で用いられる $\mathrm{O}$ はほとんどが $\Theta$ に置き換えられますが、 Big O notation と同時に説明すると混乱を招くと判断し、競技プログラミングにおいて常用されている $\mathrm{O}$ を使用しています。

$\rm best :$ 最良計算量

多くのアルゴリズムは、入力によって計算量が変化します *2。例えば、ソートアルゴリズムには大まかに $N!$ 通りの入力が存在します。あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、 $\rm best$ を付けて表記します。

線形探索は ${\rm best} \ \mathrm{O} ( 1 )$ (最初に求める値が存在した場合)
マージソートは ${\rm best} \ \mathrm{O} ( N \log N )$
挿入ソートは ${\rm best} \ \mathrm{O} ( N )$ (実装次第)

例えば、ほとんどのソートアルゴリズムは最初に列がソート済かを調べることで ${\rm best} \ \mathrm{O} ( N )$ に改善できるでしょう。 (そのような改善をして嬉しいかどうかは別の話ですが。)

$\rm worst :$ 最悪計算量

最小値を取った最良計算量に対して、最大値を最悪計算量と呼び、 $\rm worst$ を付けて表記します。

線形探索は ${\rm worst} \ \mathrm{O} ( N )$
マージソートは ${\rm worst} \ \mathrm{O} ( N \log N )$
挿入ソートは ${\rm worst} \ \mathrm{O} ( N ^ 2 )$

最悪計算量は強い保証であり、最悪計算量でアルゴリズムを見積もれば想定外に時間がかかることはありません。競技プログラミングはどのようなテストケースがあるか分からないため、最悪計算量が重要となることが多いです。特に何も書かない場合、暗黙に最悪計算量を指すことがあります。(文脈に依存します)

$\rm average :$ 平均計算量

全ての入力に対しての平均を平均計算量と呼び、 $\rm average$ を付けて表記します。

先頭の値をピボットに用いるクイックソートは ${\rm average} \ \mathrm{O} ( N \log N )$

平均的に高速なアルゴリズムは、最悪計算量が悪くても実用的な場合があります。競技プログラミングで平均計算量を信用することは必ずしも得策ではありませんが、「テストケースがランダムに生成されている」場合解法を平均計算量で評価することが可能です。逆に writer に想定されていると、平均計算量のよいアルゴリズムも最悪計算量が悪いと落とされてしまいます。

$\rm expected :$ 期待計算量

アルゴリズムの中には、実行時に乱数を生成し、乱数の出目次第で計算量が変化するアルゴリズムがあります。このとき、計算量の期待値 (平均値) を期待計算量と呼び、 $\rm expected$ を付けて表記します。平均を取るという点で平均計算量と似ているように見えますが、異なる概念です。

ピボットをランダムに選ぶクイックソートは ${\rm expected} \ \mathrm{O} ( N \log N )$
ハッシュテーブルの検索は ${\rm expected} \ \mathrm{O} ( 1 )$ *3

平均計算量との違いは、平均を取る対象が入力全体か、乱数全体かという点です。入力はしばしばランダムではないですが、乱数は常にそのランダム性が保証されています *4。よって競技プログラミング的視点では「平均計算量は hack 可能」「期待計算量は hack 不可能 *5」という特徴があります。ピボットをランダムに選ぶことで、クイックソートが期待計算量に改善されている点は興味深いと言えるでしょう。

$\rm amortized :$ 償却計算量

償却計算量とはならし計算量とも呼び、データ構造のように複数の操作を繰り返し行う場合に操作一回を解析する概念です。
例として動的配列 *6 に要素の追加を繰り返し行った際の挙動を考えてみましょう。容量が限界に達したら $\mathrm{O} ( N )$ 掛けて倍の大きさのメモリを確保し、全ての要素を移動させます。拡張のタイミングの操作は当然 $\mathrm{O} ( N )$ の計算量が掛かります。しかしこのような「重い」操作は滅多に起こらず、実際には一操作辺り平均して $\mathrm{O} ( 1 )$ の計算量しか掛かっていません。
この「平均すると速い」は平均計算量や期待計算量に近い性質ですが、どのような入力でも大丈夫ですし、運の良し悪しにも左右されません。償却計算量はこのようなアルゴリズムを評価することに向いています。
(データ構造が空の状態から) $N$ 回の操作を行った際の計算量が $f( N )$ であるとき、一操作辺りの償却計算量は ${\rm amortized} \ \frac{f( N )}{N}$ となります。

動的配列への要素の追加は ${\rm amortized} \ \mathrm{O} ( 1 )$
splay tree の各種操作は ${\rm amortized} \ \mathrm{O} ( \log N )$

償却計算量は期待計算量と同様、競プロで信頼できる計算量評価の一つです。最悪計算量は悪いが償却計算量は良いようなデータ構造には、最悪計算量が同程度のものより簡潔、高速である場合があり注目に値します。

2021/12/19 追記

上記の定義は不完全で、不都合なことが多いと感じます。償却計算量について厳密に定義した文献を見つけられていませんが、私の経験上以下のような定義だと多くのケースで整合すると思われるものを紹介します。

データ構造に対して、起こり得る操作全体を $M$ とする。操作の償却計算量が $(A _ m) _ {m \in M}$ であるとは、任意の操作列 $(m _ i) _ {i = 1} ^ {n}$ に対して

\begin{align} \text{操作列} (m _ i) _ {i = 1} ^ {n} \text{を実行する実際の計算量} \leq \sum _ {i = 1} ^ {n} A _ {m _ i} \end{align}

が成り立つことと定義する。ここで、操作列 $(m _ i) _ {i = 1} ^ {n}$ は「何もない」状態から始まるもののみを指す。つまり、最初の操作 $m _ 1$ は「空の heap を作る」や「与えられた列から、segment tree を構築する」などになる。 (この条件が無いと、重い操作 1 つからなる列の計算量が壊れてしまう)

(2021/12/19 追記終わり)

余談

期待計算量や償却計算量は最良/最悪/平均計算量と同時に存在しうる概念だと思うのですが、厳密な定義や使用例が発見できなかったので詳しく書くことは控えました。ご存知の方がいらっしゃいましたら教えて頂けると嬉しいです (記事の誤りなども)。

*1: $\rm expected$ などの修飾を計算量の前と後のどちらに付けるかはどちらの例も見られよくわからなかったため、前で統一しています

*2: $\mathrm{O}$ 記法を用いるのは「計算量のオーダー」であって、「計算量」は計算回数を指すことに注意してください

*3:一部のハッシュテーブルは $\rm worst$ で保証する

*4:現実的には疑似乱数ですが、実用的には十分にランダムです

*5:乱数の seed を hack する場合は別

*6:C++ ならば std::vector

noshi91のメモ

データ構造のある風景