引用元: 計算量について、償却/期待/平均など - noshi91のメモ

最良計算量(best)

あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、best を付けて表記します。

• 線形探索は best O(1) (最初に求める値が存在した場合)
• マージソートは best O(NlogN)

最悪計算量(worst)

あり得る全ての入力のうちの計算量の最大値。worst を付けて表記。

• 線形探索は worst O(N)
• マージソートは worst O(NlogN)
• 挿入ソートは worst O(N2)

最悪計算量は強い保証であり、最悪計算量でアルゴリズムを見積もれば想定外に時間がかかることはありません。

平均計算量(average)

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

• 先頭の値をピボットに用いるクイックソートは average O(NlogN)

期待計算量(expected)

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

• ピボットをランダムに選ぶクイックソートは expected O(NlogN)
• ハッシュテーブルの検索は expected O(1)

償却計算量(amortized)

償却計算量とはならし計算量とも呼び、データ構造のように複数の操作を繰り返し行う場合に操作一回を解析する概念です。

例として動的配列に要素の追加を繰り返し行った際の挙動を考えてみましょう。 容量が限界に達したら O(N) 掛けて倍の大きさのメモリを確保し、全ての要素を移動させます。 拡張のタイミングの操作は当然 O(N) の計算量が掛かります。 しかしこのような「重い」操作は滅多に起こらず、実際には一操作辺り平均して O(1) の計算量しか掛かっていません。

• 動的配列への要素の追加は amortized O(1)
• splay tree の各種操作は amortized O(logN)