ならし計算量は、平均ではない

この違いは教える側の便宜ではありません。C++ 標準ドラフトが、同一文書の中で2語を別の対象に割り当てています。 列コンテナ側、[sequence.reqmts] パラグラフ70。この直後に push_back などが列挙されています。

Operations other than prepend_range and append_range are implemented so as to take amortized constant time.

ハッシュ表側、[unord.req] の冒頭。

The worst-case complexity for most operations is linear, but the average case is much faster.

push_back には amortized、ハッシュ表には average case と worst case。 同じ規格が、指すものに応じて語を使い分けています。そして [vector.modifiers] が、重い回の正体を明記しています。

Complexity: If reallocation happens, linear in the number of elements of the resulting vector; otherwise, linear in the number of elements inserted plus the distance to the end of the vector.

再確保が起きた回は linear。それでも全体としては amortized constant。「1回1回は最悪 O(n) なのに、ならすと O(1)」が、規格の2条項だけで言い切れます。

なお [vector.capacity] には逃げ道の規定もあります。reserve() を呼んだ後は容量を超えるまで再確保が起きません。代価を払いたくなければ、先に確保しておけばよいということです。

実物を測りました。Python の list に20万回 append し、1回ずつ time.perf_counter_ns() で計測。再確保が起きた回は sys.getsizeof の変化で検出しました。

append 1回の中央値: 83.0 ns
append 1回の平均値: 70.1 ns
append 1回の最大値: 19208 ns (添字 9452)
合計: 14.02 ms / 200000 回 → 1回あたり平均 70.1 ns
 
再確保が起きた回の所要時間 中央値: 1312.5 ns (n=72)
それ以外の回の所要時間     中央値: 83.0 ns
 
最大値 19208 ns が 1回でも、200000回の平均は 70.1 ns
最大値 / 中央値 = 231 倍

測定環境は Apple Silicon 上の Docker、コンテナ内は Python 3.12.14 / Linux 6.10.14-linuxkit-aarch64、1環境での1回の測定です。絶対値は一般則ではありません。

読みどころは3つ。再確保の回は中央値 1312.5 ns、それ以外は 83.0 ns で約16倍。 最大の1回は 19208 ns で中央値の231倍。 それでも20万回の平均は 70.1 ns。跳ねた回の影響は、ならすと消えています。

再確保の回数も測りました。

         n      再確保回数   log2(n)
      10          3       3.3
     100         11       6.6
    1000         28      10.0
   10000         47      13.3
  100000         66      16.6
 1000000         86      19.9
 
    添字       推定容量      前回比
     0          4      nan
     4          8    2.000
     8         16    2.000
    16         24    1.500
    24         32    1.333
...
 70304      79096    1.125
 79096      88988    1.125
 88988     100116    1.125

n を10倍にしても、再確保回数は +19 / +19 / +20 しか増えません。 掛け算ではなく足し算、つまり log 的です。n=100万でも86回。だから1回あたりに割り振られる負担は、n が大きくなるほど薄まります。下段は容量の伸び方で、小さいうちは 2.0 倍ですが、大きくなると 1.125 (9/8) に収束しました。