計算量
best, worst, average
expected
平均計算量との違いは、平均を取る対象が入力全体か、乱数全体かという点です。 入力はしばしばランダムではないですが、乱数は常にそのランダム性が保証されています。 よって競技プログラミング的視点では「平均計算量は hack 可能」「期待計算量は hack 不可能 」という特徴があります 例として動的配列 に要素の追加を繰り返し行った際の挙動を考えてみましょう。 容量が限界に達したら O(N) 掛けて倍の大きさのメモリを確保し、全ての要素を移動させます。 拡張のタイミングの操作は当然 O(N) の計算量が掛かります。 しかしこのような「重い」操作は滅多に起こらず、実際には一操作辺り平均して O(1) の計算量しか掛かっていません。
この「平均すると速い」は平均計算量や期待計算量に近い性質ですが、どのような入力でも大丈夫ですし、運の良し悪し
Linked list$ O(n)でループすると$ O(n^2)で爆発