2 つの が与えられた場合std::set、単純に両方のセットを同時に反復処理して要素を比較することができ、線形の複雑さが得られます。std::unordered_set要素は任意の順序で格納される可能性があるため、これは s では機能しません。では、どのくらいの費用がかかりa == bますstd::unordered_setか?
質問する
7432 次
2 に答える
11
最悪のケースは O(n²) です。
しかし、順序付けられていないセットは、実際にはハッシュによって順序付けられています。したがって、ハッシュを比較して (これが失敗した場合、セットを等しくすることはできません)、同じハッシュ (線形) が実際に同じ値 (同じハッシュの異なる値に対して O(n²)) を持っていることを確認できます。
最良の場合、これは O(n) です。
通常、複雑さは、ハッシュ関数が「良い」(異なるオブジェクト -> 常に異なるハッシュ) 場合は O(n) になり、ハッシュ関数が「悪い」(すべてのハッシュ値が常に同じ) 場合は O(n²) になります。
于 2012-04-12T06:43:08.103 に答える
5
との複雑operator==さoperator!=:
平均的なケースでの線形の複雑さ。最悪の場合はN 2です。ここで、N はコンテナーのサイズです。
標準§23.2.5、ポイント11の詳細：
unordered_setとの場合unordered_map、 の複雑さoperator==(つまり、 の==演算子、value_typeによって返される述語、 によって
key_equal()返されるハッシャーへの呼び出しの数) は、平均的なケースでhash_function()は に比例し、最悪のケースではN 2に比例します。 .NNa.size()
于 2012-04-12T06:41:41.257 に答える