1

setやmultisetは素集合を管理するデータ構造ですが、これをset A;とset B;のように宣言して、A == Bのように比較した場合、計算量はどうなるのか疑問に思いました。
vector A;とvector B;においてA == Bの時にはイテレーター同士を比較していくと思うので、O(N)になると思うのですが、この見解についても誤っていたら教えていただきたいです。

1
  • multisetは多重集合でした。。 2022年11月30日 0:56

2 件の回答 2

2

言語仕様ではコンテナ要件 (Container requirements) として == の挙動が含まれており、計算量は線形 (つまりビッグオー記法でいうところの O(N) のこと) であることを要求しています。

つまり言語仕様中でコンテナとして定義されている型 (もちろん setmultiset を含む) はいずれも O(N) で比較できます。

2
1

cpprefjp に書いてありますね。きっと規格でもそのように定義されているのでしょう。

set operator== 計算量

size() に対して線形時間。ただし、xとyのサイズが異なる場合は定数時間。

multiset operator== 計算量

size() に対して線形時間。ただし、xとyのサイズが異なる場合は定数時間。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。